Showing no solution exists for small system of multivariate quadratics over a finite field

80 Views Asked by At

I would like to show for the system of polynomials $$ f_j(\vec{a})=\sum_{i=1}^8 a_i a_{i+j \pmod{8}} = 0, \quad j=1,2,3,4 $$

with $a_i \in \{-1,+1\}$, no common solution can exist. It is easy to confirm this by straightforward brute force calculation of all possible variable combinations.

I would like to find some clearer argument however that does not rely on computational methods, something I think ought to be possible given the highly structured nature of the problem. It is possible to find a common solution for any three out of four polynomials as in $\vec{a} = \{1,1,1,-1,1,1,1,-1\}$ which is a root for all except when $j=4$ but I can only show this in the specific instance and generalizing the inconsistency has proven difficult.

Is there a way to show this inconsistency directly from the above system of equations? The best approach I can see is via Hilbert's Nullstellenstatz which would entail finding a set of any polynomials $q_j(\vec{a})$ such that $$ \sum_{j=1}^4 q_j(\vec{a})f_j(\vec{a}) = 1. $$ I have been quite unsuccessful in this however - such a set of $q_j(\vec{a})$ certainly exist given the iff criteria of the theorem but they may be very complicated. The nice behavior of the $f_j(\vec{a})$ lead me to believe they may be quite nice.

1

There are 1 best solutions below

6
On BEST ANSWER

Here I might try the following approach.

Let's denote $$ \Theta(j):=\sum_{i=1}^8a_ia_{i+j} $$ with index arithmetic done modulo $8$ everywhere. As $a_i\in\{\pm1\}$ for all $i$, we clearly have $\Theta(0)=8$. Also, the obvious symmetry says that $\Theta(j)=\Theta(8-j)$ for $j=1,2,3,4$.

Write $$ S=a_1+a_2+\cdots+a_8. $$ If $\Theta(j)=0$ whenever $j=1,2,3,4$, then $$ \begin{aligned} S^2&=\sum_{i=1}^8\sum_{j=1}^8a_ia_j\\ &=\sum_{i=1}^8\sum_{\ell=0}^7a_ia_{i+\ell}\\ &=\sum_{\ell=0}^7\Theta(\ell)\\ &=\Theta(0)+2\Theta(1)+2\Theta(2)+2\Theta(3)+\Theta(4)\\ &=\Theta(0)=8. \end{aligned} $$ But $S$ is an integer and $8$ is not a perfect square, so this is a contradiction.