All Questions
Tagged with co.combinatorics finite-fields
22 questions
13
votes
2
answers
1k
views
Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?
Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ?
I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate ...
- 24.9k
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
23
votes
4
answers
3k
views
Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...
- 118k
10
votes
1
answer
807
views
How many Lie and associative algebras over a finite field are there?
This question is related to the following general question:
Given a variety of (non-associative) algebras $\mathcal V$, a finite field $\mathbb{F}_q$, with $q$ elements, and a positive integer $n$, ...
- 398
22
votes
1
answer
970
views
Grothendieck on polyhedra over finite fields
In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most ...
- 528
16
votes
3
answers
2k
views
Periodic orbits and polynomials
There are two simple and classic enumerations that still I'm puzzled about. Let's start with a simple counting problem from a well-known dynamical system.
fact 1 Consider the "tent map" f:[0,1]→[...
- 60.5k
16
votes
2
answers
1k
views
Examples of problems where considering "discrete analogues" has provided insight or led to a solution of the original problem
The Kakeya conjecture posits that any Kakeya set in $\mathbb{R}^n$ has dimension $n$.
A discrete (finitized?) version of this problem is the Finite Field Kakeya conjecture, which was proved by Dvir ...
14
votes
2
answers
655
views
Number triangle
This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
- 1,216
13
votes
1
answer
468
views
Near-linear mappings from $\mathbb F_p$ to $\mathbb R$
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\R}{{\mathbb R}}$
$\renewcommand{\phi}{\varphi}$
Let $p\ge 5$ be a prime.
If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
- 23k
11
votes
2
answers
788
views
Blocking sets in three dimensional finite affine spaces
What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?
Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0,...
- 1,197
10
votes
1
answer
561
views
How many rich directions does a set in $\mathbb F_p^2$ determine?
$\newcommand{\F}{\mathbb F}$
A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.
A set of size $|P|&...
- 23k
9
votes
1
answer
425
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 6,741
8
votes
0
answers
304
views
A strong sum-product "for translates" in finite fields
In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...
- 11.2k
7
votes
0
answers
276
views
Cyclic shift acting on finite Grassmannian
The (twisted) cyclic shift $(v_1,v_2,\ldots,v_n) \mapsto (v_2,v_3,\ldots,v_n,(-1)^{k-1}v_1)$ acting on the Grassmannian $\mathrm{Gr}(\mathbb{C};k,n)$ of $k$-planes in $\mathbb{C}^n$ is an important ...
- 24.2k
5
votes
1
answer
447
views
More expanders?
Having received several exhausting answers to my recent question about
the expansion properties of a certain graph, I now wonder whether anything is
known on the following graphs of a similar nature:
...
- 23k
5
votes
1
answer
459
views
$(n-2)$-blocking sets in $AG(n,2)$
Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$.
I have seen a lot work related to minimal $(n-1)$-blockings set.
...
- 337
4
votes
1
answer
266
views
Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
This question is a follow-up of this question.
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.
Question: Can we compute the exact minimum $$A:=
\min_{u:\mathbb{...
- 6,741
4
votes
1
answer
317
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 13.9k
3
votes
2
answers
235
views
Largest $A\subset \mathbb{F}_2^n$ such that no two $a\neq b$ in $A$ add to an element of $A.$
If such a set $A$ of size $m$ exists, all its admissible pairwise sums must lie in its complement, thus
$$
\binom{m}{2} \leq 2^n-m,
$$
which gives $$m\leq 2^{(n+1)/2}\qquad (1)$$.
Edit: The upper ...
- 10.4k
2
votes
0
answers
337
views
Enumerating certain types of permutation polynomials
Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for all ...
- 1,197
1
vote
0
answers
88
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.9k
1
vote
1
answer
153
views
Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$
Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square.
Through the determinant ...
- 13.9k