__
TR94-015 | 12th December 1994 00:00
__

#### Symmetric Systems of Linear Equations modulo $p$

**Abstract:**

Suppose that $p$ is a prime number $A$ is a finite set

with $n$ elements

and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the

elements of

$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an

$n$ is sufficiently large.) We will consider systems of linear equations

modulo $p$ of the form $\sum u_{a}^{(i)}x_{a}\equiv b_{i}$ (mod p),

$i=1,...,l$. We will call such a system symmetric if for every

permutation $\pi$ of the set $A$ and for every $i=1,...,l$ the equation

$\sum u_{a\pi}^{(i)}x_{a}=b_{i}$ is also an equation of the system.

We show

that if such a system has a solution then it also has a solution which

is definable by a first-order formula $\phi$ whose length depends only

on $k$ and $p$ over the structure ${\cal A}=[A, \le,

R_{1},...,R_{p^{j}}] $ defined in the following

way. Let $\le $ be a linear ordering of the universe and $j$ a positive

integer sufficiently large with respect to $k$ and $p$. For each

$i=1,...,p^{j}$, $R_{i}$ is a unary relation on $a$, $R_{i}(x)$ holds

iff $x$ is the $r$th element of $A$ and $r\equiv i$ (mod p). More

precisely the expression that the solution $t_{a}$, $a\in A^{k}$ is

first-order definable means that for each $c=0,1,...,p-1$ the set $\lbrace

a\in A|$$ t_{a}\equiv c$ (mod p) $\rbrace $ is definable by a first-order

formula $\phi_{c}$ whose length remains below a bound depending only on

$k$ and $p$.