Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR94-015 | 12th December 1994 00:00

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

TR94-015
Authors: Miklos Ajtai
Publication: 12th December 1994 00:00
Keywords:

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$.

ISSN 1433-8092 | Imprint