# How many rich directions does a set in $\mathbb F_p^2$ determine?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.

A set of size $|P|>p$ determines all $p+1$ directions, a set of size $|P|\le p$ not contained in a single line determines at least $(|P|+3)/2$ directions; the former is an immediate consequence of the pigeonhole principle, the latter is a highly non-trivial result of Szonyi that builds on works of Rédei.

Let's say that a direction in $\F_p^2$ is rich if there is a line in this direction containing at least three points of $P$. If $P$ is trapped in a line, or a union of two lines, then there are just one or two rich directions.

What is the smallest possible number of rich directions for a set $P\subset\F_p^2$ of size $\frac53\,p<|P|\le 2p$ given that $P$ is not contained in a union of two lines?

It is easy to construct sets $P$ with about $|P|-p$ rich directions, but it is not clear to me how much better can one do.

The largest possible number of points in general position in $\F_p^2$ is $p+1$, which is quite easy to prove; thus, we are guaranteed to have at least one rich direction. Indeed, I can show that if $\frac32(1+\delta)p\le|P|\le 2p$, then there are at least $\Omega_\delta(\sqrt p)$ rich directions, but I suspect that this can be far from being sharp.

• Why $\frac53$ ? – Noam D. Elkies May 1 '18 at 21:04
• For p>3 and |P|=2p it is possible to have only |P|-p-1=p-1 rich directions, with the following construction: P'={(h,k): h\in{0,1} k\in F_p}, P=P'\cup{(-1,0),(2,2)}\setminus{(0,0),(2,1)}. – Luca Ghidelli May 2 '18 at 4:39
• For p=7 and |P|=14 it is even possible to have only 5=p-2 rich directions! With the following construction: P'={(0,k): k\in F*_7}\cup{(k,0): k\in F*_7}, P=P'\cup{(5,5),(5,6),(6,5)}. It looks like the optimal values interpolates the function (p+3)/2... – Luca Ghidelli May 2 '18 at 4:44
• @NoamD.Elkies: any range $(2-\epsilon)p<|P|\le 2p$ with $\epsilon>0$ fixed is fine for my purposes. – Seva May 2 '18 at 5:37

A cool generalization of Rédei's method furnishes the following lower bound:

Theorem-lower bound. Let $U\subset \mathbb F_p$ have cardinality $2p$. Then $U$ is contained in the union of two lines or it determines at least $\lfloor\frac{p+4}{3}\rfloor$ rich directions.

The key idea is to consider the y-derivative of the Rédei polynomial $$H_{U}(x,y):=\prod_{(a,b)\in U} (x-ay+b) = x^{2p}+h_1(y)x^{2p-1}+\dots+h_{2p}(y)$$ and the following proposition on lacunary fully reducible polynomials:

Proposition Let $p\neq 2$ be prime and let $f(x)\in\mathbb F_p[x]$ be a (monic) fully reducible polynomial of degree $2p$. Write $f(x)=x^{2p}+g(x) x^p + h(x)$ with $deg(g)=m$, $deg(h)=n$ and $m,n<p$. Then either $$max(n,m+1)+m>p$$ or $f(x)$ is one of the following: $f(x)=(x^p-x)^2$ or $f(x)=(x-t)^p(x-s)^p$ or $f(x)=(x^p-x)(x-t)^p$ for some $s,t\in\mathbb F_p$.

Fully reducible means that it factors completely, as a product linear factors, over $\mathbb F_p$. The Theorem should be compared to the following Example.

Example-upper bound. For every odd prime $p$ there is a set $P\subseteq \mathbb F_p^2$, with cardinality $|P|=2p$ that determines exactly $(p+3)/2$ rich directions, and which is contained in 3 lines but not in 2 lines.

Remarks The theorem is of course optimal up to multiplicative constant, but I do not know if it is actually close to be sharp. To see if it is, I suggest to think first about this MO problem. Following Szonyi, it is not difficult to get a result valid for $|U|<2p$. Essentially, all is needed is to prove the version of the Proposition corresponding to almost-fully-reducible $f(x)$. The theorem seems to generalize to counting $n$-rich directions, while the proposition suggests interesting generalizations to lacunary almost-fully reducible polynomials of degree $np$. It would be cool to apply them to blocking-set problems. Question: can the Proposition be proved more directly from the corresponding classical result for lacunary polynomials of degree $p$? Last thing: Rédei-s theorem has a proof that avoids lacunary polynomials due to Lovász, L., and A. Schrijver, but I have been unable to generalize their method.

Proofs follow

Proof of the Proposition

Let $F(x) = gcd(f(x),x^p-x)$, then $$F(x)\ |\ xg(x)+h(x)+x^2$$ because $xg(x)+h(x)+x^2=f(x)-(x^p-x)(x^p+x+g(x))$ and $$\frac{f(x)}{F(x)}\ |\ f'(x) = g'(x)x^p + h'(x).$$ Therefore $f(x) | (g'(x)x^p + h'(x))(xg(x)+h(x)+x^2)$.

Case1: $(g'(x)x^p + h'(x))(xg(x)+h(x)+x^2)\neq 0$. Then $2p\leq m-1+p+N$ with $N:=max(n,m+1,2)$.

Case2: $g'(x)x^p + h'(x)+0$. Then $f(x)=(x^2+g(0)x+h(0))^p=(x-t)^p(x-s)^p$.

Case3: $h(x)=-xg(x)-x^2$. Then $f(x)=(x^p+g(x)+x)(x^p-x)$. By Rédei's proposition on lacunary fully reducible polynomials of degree $p$, we have either $x^p+g(x)+x=(x-t)^p$, or $x^p+g(x)+x=x^p-x$, or $2m\geq p+1$. Here $n=m+1$.

Proof of the Theorem Let $D$ be the set of rich directions determined by $U$. Without loss of generality we may assume that $\infty\in D$ (i.e. that there is a vertical line $X=c$ containing $\geq 3$ points of $U$. See for example Seva's addendum, May 4, 2018). Notice that for fixed slope $y\in \mathbb F_p$ we have that $(x-ay+b)=(x-a'y+b')$ if and only if $y=\tfrac{b-b'}{a-a'}$.

Thus $y\not \in D$ if and only if $$H_U(x,y)=\prod_{k\in\mathbb F_p}(x-k)^2=x^{2p}-2x^{p+1}-x^2.$$ In particular for $j\neq p-1,2p-2$ the polynomial $h_j(y)$ vanishes at least at $p+1-|D|$ values of $y$ (i.e. $y\not\in D$). Since $deg(h_j)\leq j$, we have that $h_j(y)\equiv 0$ identically for $j=1,\ldots,p-|D|$.

Now the y-derivative trick to gain vanishing Consider the y-derivative $$\partial_y H_U(x,y) = h'_1(y)x^{2p-1}+\dots+h'_{2p}(y).$$ By Leibniz formula we see that for $y\not \in D$ we have that $H_U(x,y)$ is divisible by $(x-k)$ for all $k\in\mathbb F_p$. In other words $$H_U(x,y) = (x^p-x)S_y(x) = S_y(x)x^p-S_y(x)x$$ for some polynomial with $deg(S_y)\leq p-1$. We deduce for $j=2,\ldots,p-1$ and $y\not \in D$ the equality $h'_j(y)=h'_{j+p-1}(y)$.

Since $h_j(y)\equiv 0$ identically for $j=1,\ldots,p-|D|$, we get that $h_{p+j}$ vanishes at $y\not\in D$ with order 2 for $j=1,\ldots,p-|D|-1$. Therefore $h_{p+j}(y)\equiv 0$ identically as soon as $2(p+1-|D|)\geq p+j+1$. As a consequence, for all $y\in \mathbb F_p$ we have $$H_U(x,y) = x^{2p} + g(x)x^p+h(x)$$ with $deg(g)\leq |D|-1$ and $deg(h)\leq 2(|D|-1)$.

Take $y\in\mathbb F_p$.

1. $H_U(x,y)=(x^p-x)^2$ when $y\not\in D$;
2. $H_U(x,y)=(x-s)^p(x-t)^p$ when $U$ is the support of the two lines $Y=yX+s$, $Y=yX+t$;
3. $H_U(x,y)=(x^p-x)(x-t)^p$ means in particular that $p$ points of $U$ are on the line $Y=yX+t$.

It is not difficult to show that, if $U$ is not supported on two lines only, then here is a line containing at least 3 points of $U$ but less than $p$ points. Such line corresponds to $y=y_0\in D$ for which 1-2-3 above do not hold.

By the Proposition applied to $f(x)=H_U(x,y_0)$ we get $3(|D|-1)\geq p+1$, so the Theorem.

Proof of the Example. Let $P'=\{(k,k^{\frac{p+1}2}): k\in\mathbb F_p\}$, which is a set contained in the two lines $y=\pm x$ with cardinality $|P'|=p$. It is shown in [1] that $P'$ attains the equality in the theorem of Rédei. In other words, $P'$ determines exactly $(|P'|+3)/2=(p+3)/2$ directions.

Now let $P''=\{(k,k-2): k\in\mathbb F_p\}$, i.e the line parallel to $y=x$ passing through $(1,-1)$. We observe that $P'\cap P''=\emptyset$ and that the direction of $P''$ is one of the directions determined by $P'$.

Finally we let $P=P'\cup P''$ and we observe immediately that the rich directions of $P$ are exactly the directions determined by $P'$.

[1] Lovász, L., and A. Schrijver. "Remarks on a theorem of Rédei." Studia Scient. Math. Hungar 16.449-454 (1981): 15-32.

• Thanks, this is interesting, but I actually need a lower bound: what is the number of rich directions that any set $P$ is guaranteed to determine? – Seva May 2 '18 at 5:41
• And, BTW, why do you say "in the theorem of Redei"? Isn't it a theorem of Szonyi? – Seva May 2 '18 at 5:43
• The case |P|=p is already a theorem of Rédei and Megyesi (I think I should have included him as well). The theorem of Szonyi is the generalization to |P|<p. The argument I wrote can be used with |P'|<p, but I don't know what are the cases of equality in Szonyi's theorem. – Luca Ghidelli May 2 '18 at 13:01
• Oh, I see, thanks for the clarification; so, the result is essentially due to Redei, with some contribution by Megyesi, appeared first in Redei's book. BTW, as far as I understand, Szonyi's result cannot be derived from Redei-Megyesi using the latter as a "black box"? – Seva Jun 5 '18 at 6:36
• This is a great bound. I cannot recall now what application I had in mind (if any), but I certainly believe that this rich directions problem is interesting in its own rights. Interestingly, I have a somewhat incomplete argument (hopefully, it can be completed) which gives the same bound $p/3$ for sets of size $|P|=2p$ (but does not work for smaller sets). – Seva Jun 6 '18 at 14:33