Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-015 | 12th December 1994 00:00

Symmetric Systems of Linear Equations modulo p

RSS-Feed

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 rth 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