4
$\begingroup$

$\newcommand{\F}{\mathbb F}$ Suppose that $p$ is a prime, and $k<p/2$ a positive integer.

Consider a system of $k$ distinct directions in the affine plane $\F_p^2$, and the system of $k$ pencils corresponding to these directions, each pencil consisting of the $p$ parallel lines in the associated direction. Suppose, further, that the $p$ lines of every pencil are assigned some integer weights in a non-uniform way; that is, the lines of a pencil cannot all share the same common weight. To every point $x\in\F_p^2$ there corresponds a unique line from every pencil containing $x$, and we define the weight of $x$ to be the sum of the weights of these $k$ lines. How many zero-weight points can there be?

It is immediately seen that for $k=1$ we must have at least $p$ points with non-zero weights. Also, it is quite easy to see that for $k=2$ there are at least $2p-2$ such points. For $k=3$ it is not difficult to assign the weights so that there are $3p-5$ non-zero-weight points, which is best possible for $p$ large enough. In general, taking a system of $k$ lines in a general position and assigning the weight $1$ to about half of them, the weight $-1$ to the remaining half, and the weight $0$ to all parallel lines, we get as few as $kp-\frac34k^2+\frac12k+\delta$ points with non-zero weights, with $\delta=0$ for $k$ even and $\delta=\frac14$ for $k$ odd. Can one have even fewer non-zero-weight points?

For my purposes, it would actually suffice to show that there are at least $2(p+1-k)$ points with non-zero weights. On the other hand, I cannot assume anything beyond $1<k<p/2$.

$\endgroup$
  • $\begingroup$ for k=1 we must have at least p points with non-zero weights; it would actually suffice to show that there are at least 2(p+1−k) points with non-zero weights; I cannot assume anything beyond k<p/2. So how do you consolidate these 3 statements? $\endgroup$ – fedja May 29 '18 at 22:52
  • $\begingroup$ @fedja: You are right: I believe that the case $k=1$ is special (it is not of much interest, anyway), and I also suspect that the case $k=2$ can be critical, in the sense that the smallest possible number of non-zero weights gets only larger as $k$ grows. Anyway, I will slightly edit the question now to avoid any ambiguity. $\endgroup$ – Seva May 30 '18 at 6:08
  • 1
    $\begingroup$ Indeed, it looks so though the lower bound of $p$ is trivial for every $k<p/2$. You just need to double it somehow... $\endgroup$ – fedja May 30 '18 at 6:23
  • $\begingroup$ At the very least you should be able to show that if you take $p$ points in $\mathbb Z_p^2$ not all on one line, then there are at least $p/2$ different slopes formed by the lines passing through pairs of those points. Can you do that? I spent a couple of days (when driving) on this particular question to no avail so far. $\endgroup$ – fedja May 31 '18 at 23:46
  • $\begingroup$ @fedja: There are actually at least $(p+3)/2$ directions. This is a known result of Rédei and Megyesi, with a rather non-trivial proof; certainly not something one can do in a couple of days when driving. It was independently rediscovered by Dress, Klin, and Muzychuck in 1993. How is it related to the present problem? Also, what is the trivial way to get $p$ as a lower bound? (I knew two easy ways to get $p$ or $p-1$, but cannot recall any of them now.) $\endgroup$ – Seva Jun 1 '18 at 8:33
1
$\begingroup$

OK, here goes. Let $p+1-k=\ell$. If you have any from $\ell$ directions not from your pencils, then the sums along the lines in that direction should not depend on the line and (since the whole sum over $\mathbb F_p^2$ is fixed), not on the direction either. This is the only property we'll use below. Let us call this line sum $S$. You want to find $2\ell$ non-zero values.

Case 1: $S=0$

Since the functions you add are orthogonal modulo constants, you cannot have an identically constant function in the end, so there is some nonzero number somewhere. Assume it is positive. Then on each of $\ell$ lines through the corresponding point there should be a negative number. Thus the negative numbers are at least $\ell$. Take one of them and run the same argument to conclude that there are at least $\ell$ positive numbers too.

Case 2: $S\ne 0$:

This is where the real fight is. Assume for definiteness that $S>0$.
Note that if for some present value $y$ the value $S-y$ is not present, then each of $\ell$ lines through $y$ contains at least $2$ other non-zero numbers and we get $2\ell$ immediately.

Assume that there are negative numbers. Let $x<0$ be the least of them. Then $S-x$ is present and is the largest value in the game. Let $a$ be the number of $x$, $b$ the number of $S-x$ and $c$ the number of everything else. Now take any line through $x$ that does not contain $S-x$. There are at least $\ell-b$ such lines and each of them contains at least $2$ numbers not in $\{x,S-x\}$ (here is where I use that $x$ is the least and $S-x$ the largest value and that $x<0$, so adding $x$'s to the line only makes it harder to recover). Thus $c\ge 2(\ell-b)$. Arguing in the same way about the lines through $S-x$ not containing $x$, we get $c\ge 2(\ell-a)$. Averaging, we get $c\ge 2\ell-a-b$ and we are done again.

Thus every non-zero value is positive. In particular, any line through $S$ cannot contain any non-zero value.

Let now $u$ be the number of $S$ and $v$ the number of everything else. Since every line in our $\ell$ directions passing through something other than $0$ or $S$ should contain at least $2$ non-zero values, we have $u+\frac v2\ge p$.

Now again 2 cases

Case 2a: The points with the value $S$ do not lie on a single line. Then we have the inequality $\frac{u+3}2+\ell\le p+1$ (because all directions determined by those points are not among our $\ell$ directions). Thus $u\le 2p-2\ell-1$, $v\ge 2(p-u)$, so $u+v\ge 2p-u\ge 2\ell+1$.

Case 2b: The $u$ points are on the same line. If $u=p$, then there cannot be anything else anywhere, so this configuration is the one with a single pencil, which we excluded. Otherwise $u<p$, so $u+v>p$ and we have some point with non-zero value not on that line. That point determines $u$ directions to the points with value $S$ that cannot be our $\ell$ directions. Thus $u+\ell\le p+1$, $v+u\ge 2p-u\ge p-1+\ell\ge 2\ell$.

The only non-trivial case is $2a$. But it has to be so because the property I mentioned in the beginning characterizes the functions that are sums of $\le p+1-\ell$ pencils of your type, so if we could find $p$ points not on one line with $<p/2$ directions, that would be a counterexample to your statement. That's why I asked about it.

$\endgroup$
  • $\begingroup$ Very interesting, I'll have to read more carefully yet; thanks! $\endgroup$ – Seva Jun 1 '18 at 14:19
  • $\begingroup$ The last paragraph is still unclear to me. Suppose we have a set $P$ of $|P|=p$ points not in a line determining less than $p/2$ directions. What are the "pencil directions" (those not determined by $P$?) and exactly how you assign the weights to the lines of the pencils to get a contradiction with the $2(p+1-k)$ bound? $\endgroup$ – Seva Jun 1 '18 at 19:28
  • $\begingroup$ @Seva Yes, the directions not determined by $p$. The weights on the pencils can be just read from the resulting function because constants and mean zero pencils form an orthogonal decompositions of $\ell^2(\mathbb F^2)$ and the projectors are just averagings over the pencil lines (for the mean 0 components, constants can be added to any term you want). At last, $p<2(p+1-k)$ for $k<\frac p 2$ $\endgroup$ – fedja Jun 1 '18 at 22:19
  • $\begingroup$ @Seva Sorry, I should have said "the directions determined by $P$"" $\endgroup$ – fedja Jun 2 '18 at 12:10
  • $\begingroup$ Interestingly, this shows that the bound $2(p+1-k)$ gives a new proof of the Rédei-Megyesi result. I wonder whether it is possible to prove Szonyi's generalization ((n+3)/2 directions for an n-element set, n≤p) this way. $\endgroup$ – Seva Jun 5 '18 at 6:29

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.