3
$\begingroup$

Let $\mathcal L$ denote the set of all lines in $\mathbb F_p^2$ parallel to one of the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\colon z\in\mathbb F_p \}. $$ Given a set $S\subseteq\mathbb F_p^2$, with every element $s\in S$ associate a formal variable $x_s$, and consider the system of homogeneous linear equations $$ \sum_{s\in S\cap\ell} x_s = 0,\quad \ell\in\mathcal L; $$ thus, there are $|\mathcal L|=3p$ equations and $|S|$ variables. What is the smallest possible size of the set $S$ for which this system has a solution with all variables $x_s$ distinct from $0$, given that $S$ meets every line in $\mathbb F_p^2$? Are there any sets of size $|S|<3p$, meeting every line, for which there are such "nowhere-zero solutions"? If so, can these sets be characterized in a comprehensible way?

$\endgroup$
  • $\begingroup$ If I've understood correctly, would $S=\{(0,0),(1,0),(2,1),(2,2),(1,2),(0,1)\}$ have the obvious nontrivial solution given by alternating values for the points in the order listed? $\endgroup$ – user44191 Jun 21 '18 at 19:35
  • $\begingroup$ @user44191: Absolutely. I oversimplified the problem trying to make it more appealing. I've made an edit to fix the issue. $\endgroup$ – Seva Jun 21 '18 at 19:53
  • $\begingroup$ Are the variables $x_s$ interpreted as real variables or could they take values from some finite abelian group? $\endgroup$ – Aaron Meyerowitz Jun 21 '18 at 22:39
  • $\begingroup$ Is there a natural way to rephrase this in terms of the finite projective plane? $\endgroup$ – user44191 Jun 21 '18 at 22:40
  • $\begingroup$ @AaronMeyerowitz: complex / real /rational / integer - all are equivalent for this problem. $\endgroup$ – Seva Jun 22 '18 at 6:04
3
$\begingroup$

What you want is not possible for $p=3$ but I have an example for $p=5.$ It satisfies a stronger condition given at the end which makes sense for any $n \times n$ matrix.

$$\left[ \begin {array}{ccccc} 3&1&-1&-1&-2\\ 0&-3&0& 1&2\\ -1&1&0&0&0\\ -1&0&1&0&0 \\ -1&1&0&0&0\end {array} \right] $$

Here the origin is at the top left so the lines parallel to $y=x$ are labelled

$$ [3, -3, 0, 0, 0],[1, 0, 0, 0, -1], [-1, 1, 0, -1, 1], [-1, 2, -1, 0, 0], [-2, 0, 1, 1, 0]$$

This was somewhat ad hoc. I'll make a few not especially deep comments and then explain how I got it.

You have a system of $3p$ simultaneous equations in $p^2$ variables. However two are redundant. This means some $p^2-3p+2$ variables can be freely chosen and these uniquely determine the other $3p-2.$ Given such a set of $p^2-3p+2$ free variables (of course there are many) we know that not all of them can be set to $0$ since that will force the all $0$ solution. Setting one of the free variables to $1$ and the rest to $0$ will yield at most $3p-1$ non-zero variables, perhaps less. However the condition that no affine line be bad in that it is labelled with all zeros may fail. If so, then setting one or more free variables to non-zero values may decrease the number of bad lines and perhaps still keep the number of non-zero variables under $3p.$

I tried this with $p=5.$ The $25$ points are as follows (so the point $(i,j)$ is $a_{5i+j+1}$

$$\left[ \begin {array}{ccccc} a_{{1}}&a_{{2}}&a_{{3}}&a_{{4}}&a_{{5}} \\ a_{{6}}&a_{{7}}&a_{{8}}&a_{{9}}&a_{{10}} \\ a_{{11}}&a_{{12}}&a_{{13}}&a_{{14}}&a_{{15}} \\ a_{{16}}&a_{{17}}&a_{{18}}&a_{{19}}&a_{{20}} \\ a_{{21}}&a_{{22}}&a_{{23}}&a_{{24}}&a_{{25}} \end {array} \right]$$

One set of free variables with a candidate assignment is

$a_{{12}}=1,a_{{13}}=a_{{14}}=a_{{15}}=a_{{17}}=a_{{18}}=a_{ {19}}=a_{{20}}=a_{{22}}=a_{{23}}=a_{{24}}=a_{{25}}=0. $

However that leads to $$ \left[ \begin {array}{ccccc} 1&0&0&0&-1\\ 0&-1&0&0& 1\\ -1&1&0&0&0\\ 0&0&0&0&0 \\ 0&0&0&0&0\end {array} \right] .$$

To fix the bottom two horizontal lines I also made $a_{18}=a_{22}=1.$ (Why those? Just a choice of one from each.) That gave the pattern at the top:

$$\left[ \begin {array}{ccccc} 3&1&-1&-1&-2\\ 0&-3&0& 1&2\\ -1&1&0&0&0\\ -1&0&1&0&0 \\ -1&1&0&0&0\end {array} \right] $$


As nicely noted by @user44191, the fact that the first row has no zero entries means that every non-horizontal line has a non-zero entry. In fact it shows that a seemingly stronger condition is satisfied. I mention it because the fact that $p$ is prime is not essential to the problem. The condition is:

In an $n \times n$ matrix $M$ define a line to be any of these $2n+n!$ sets of $n$ entries: a row, a column or $m_{1,\sigma(1)},m_{2,\sigma(2)},\cdots , m_{n,\sigma(n)}$ where $\sigma$ is a permutation.

The goal is to find an $n \times n$ matrix with $3n-1$ or fewer non-zero entries such that

  • The sums along each row and column are $0.$
  • The sums along the main diagonal and the diagonals "parallel" to it are $0.$
  • every line has a non-zero entry.

I suspect that a symmetric example is possible for any not too small $n.$

$\endgroup$
  • $\begingroup$ I have yet to check carefully your construction, but I would not be surprised if there are examples of some general sort ($p>5$). $\endgroup$ – Seva Jun 22 '18 at 6:08
  • 2
    $\begingroup$ As a note, the fact that all other lines contain an element of $S$ is pretty clear. Either they are horizontal or they contain an element of the first line; the first line is entirely nonzero, and none of the horizontal lines are zero. $\endgroup$ – user44191 Jun 22 '18 at 12:06
  • $\begingroup$ Yes, that is indeed pretty clear! There should be an easy proof based on that. $\endgroup$ – Aaron Meyerowitz Jun 22 '18 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.