Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

Sauermann, Lisa

doi:10.1007/s00208-022-02391-y

Abstract

Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ $a_{j, 1} x_{1} + \dots + a_{j, k} x_{k} = 0$ for$$j=1,\dots ,m$$ $j = 1, \dots, m$ with coefficients$$a_{j,i}\in \mathbb {F}_p$$ $a_{j, i} \in F_{p}$ . Suppose that$$k\ge 3m$$ $k \geq 3 m$ , that$$a_{j,1}+\dots +a_{j,k}=0$$ $a_{j, 1} + \dots + a_{j, k} = 0$ for$$j=1,\dots ,m$$ $j = 1, \dots, m$ and that every$$m\times m$$ $m \times m$ minor of the$$m\times k$$ $m \times k$ matrix$$(a_{j,i})_{j,i}$$ ${(a_{j, i})}_{j, i}$ is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$ $A \subseteq F_{p}^{n}$ of size$$|A|> C\cdot \Gamma ^n$$ $| A | > C \cdot Γ^{n}$ contains a solution$$(x_1,\dots ,x_k)\in A^k$$ $(x_{1}, \dots, x_{k}) \in A^{k}$ to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$ $x_{1}, \dots, x_{k} \in A$ are all distinct. Here,Cand$$\Gamma $$ $Γ$ are constants only depending onp,mandksuch that$$\Gamma $Γ < p$ . The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$ $x_{1}, \dots, x_{k}$ in the solution$$(x_1,\dots ,x_k)\in A^k$$ $(x_{1}, \dots, x_{k}) \in A^{k}$ to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$ $x_{1}, \dots, x_{k}$ are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

More Like this