Cardinality of $A_n=\{ x \in \mathbb{F}_{5}^{n} : x\cdot x=0\}$

60 Views Asked by At

Let $A_n=\{ x \in \mathbb{F}_{5}^{n} : x\cdot x=0\}$. Show that $|A_n|=(1/5+f(n))5^{n}$ where $\lim_{n \to \infty} f(n) = 0$.

Notation: The ring $(\mathbb{F}_5^{n},+,*)$ have elements of the form $(x_1,\ldots,x_n)$,$x_i \in \mathbb{F}_5$, $\mathbb{F}_{5}$ is the field $\mathbb{Z}/5\mathbb{Z}$, $|A|$ denotes the cardinality of the set $A$ and $x\cdot x = x_1^2+\ldots+x_n^2$ . Life would have been easy if the map $\phi: \mathbb{F}_{5}^{n} \to \mathbb{F}_5$ defined by $\phi(x) = x\cdot x$ was a ring homomorphism, but sadly that is not the case. I am not even sure how to start. Any hints?

1

There are 1 best solutions below

0
On BEST ANSWER

One possibility is to prove the statement using combinatorial arguments.

Denote by $M_n(b) = |\{x \in \mathbb{F}_5^n:x\cdot x = b\}|$ the set of vectors with inner product equal to $b \in \mathbb{F}_5$. We will establish a recursion on $M_n(b)$ as follows. We can write, for example, $$ M_{n+1}(0) = M_n(0) + 2M_n(1) + 2M_n(4), $$ since $x_{n+1}^2$ can only take values in $\{0,1,4\}$, where the values $1$ and $4$ are assumed with multiplicity 2 for $x_{n+1}=1$, $x_{n+1}=4$ and for $x_{n+1}=2$, $x_{n+1}=3$. In general, we have $$ M_{n+1}(b) = M_n(b) + 2M_n(b-1) + 2M_n(b+1) $$ and thus we can deduce the following recursion, $$ \begin{pmatrix}M_{n+1}(0)\\M_{n+1}(1)\\M_{n+1}(2)\\M_{n+1}(3)\\M_{n+1}(4) \end{pmatrix} = \begin{pmatrix} 1&2&0&0&2 \\2&1&2&0&0\\0&2&1&2&0 \\ 0&0&2&1&2 \\ 2&0&0&2&1 \\ \end{pmatrix} \begin{pmatrix}M_{n}(0)\\M_{n}(1)\\M_{n}(2)\\M_{n}(3)\\M_{n}(4) \end{pmatrix}. $$ The claim then follows from the standard analytical combinatorics arguments using the fact that the largest Eigenvector of the recursion matrix is 5.

I hope this is explicit enough and helps you to figure out the complete proof.