3
votes
0answers
125 views

What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
6
votes
0answers
295 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
2
votes
1answer
101 views

Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the ...
8
votes
1answer
270 views

A Balog-Szemeredi-Gowers-type question

A nice Lemma due to Konyagin asserts that for any subset $B \subset \mathbb{F}_p$ holds $$ |B.B - B.B + B.B - B.B + B.B - B.B| \geq \frac{1}{2}\min\{p, |B|^2 \}, $$ where the standard notation for the ...
14
votes
1answer
191 views

Do mutually dual finite vector spaces have the same orbit cardinalities under a linear group action?

Let $G$ be a finite group acting linearly on a finite dimensional vector space $V$ over a finite field. By Burnside's lemma, $$ |V/G| = \frac 1{|G|} \sum_{g\in G} q^{\dim(ker(g - I))}. $$ Since $g-I$ ...
1
vote
1answer
145 views

probability of having linearly independent sparse vectors over finite fields

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as ...
6
votes
2answers
317 views

Dimension of incomplete matrix over finite fields.

Hi, Suppose one has an incompletely specified $2^n \times 2^n$ matrix over some fixed finite field $\mathbb{F}_{p^k}$. In fact, one knows that the diagonal entries are zero and all other entries are ...
5
votes
1answer
361 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: ...
10
votes
2answers
320 views

An expander (?) graph

For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless $z=0$). I was told that this graph is known to be ...
16
votes
4answers
901 views

A mixing property for finite fields of characteristic $2$

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself. Let ${\mathbb F}$ be a finite field, and suppose ...
8
votes
2answers
364 views

A mixing property of linear map over finite fields

Let $F$ be a finite field of odd size $q$, and $\phi_0 : F \mapsto F$ be any map from $F$ to itself. For each $a \in F$, set $\phi_a : x \in F \mapsto \phi_0 (x) + ax $. When $\phi_0 : x \mapsto x^2 ...
0
votes
0answers
220 views

Combinatorial Interpretation of an Extension of Gaussian Polynomials

It is well-known that the Gaussian polynomial (or Gaussian coefficient, q-binomial coefficient) $\binom{n}{k}_q$ counts the number of $k$-dimensional subspaces of an $n$-dimensional vector space over ...
19
votes
2answers
1k views

Sums of powers mod p

For prime $p > 7$ with $p-1=rs$, $r>1$, $s>1$, let $A=\{x^r|x \in \mathbb{Z}_p\}$ and $B = \{x^s|x \in \mathbb{Z}_p\}$. If $g$ is a primitive root mod $p$ then $A = \{0\} \cup \{g^{ir}|0 \leq ...
10
votes
3answers
842 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" ...
6
votes
3answers
405 views

A quadratic form

Let $q$ be a power of 2. Let $P$ be the set of polynomials in $F_q [x]$ of degree d or less. Let $\mathbb{Z}$ be the ring of integers. For any $f \in P$, let $\psi(f)$ be the number of distinct ...
12
votes
4answers
1k 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 ...