10
$\begingroup$

$\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.

Added May 04, 2018

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.

$\endgroup$
  • $\begingroup$ Why $\frac53$ ? $\endgroup$ – Noam D. Elkies May 1 '18 at 21:04
  • $\begingroup$ 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)}. $\endgroup$ – Luca Ghidelli May 2 '18 at 4:39
  • $\begingroup$ 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... $\endgroup$ – Luca Ghidelli May 2 '18 at 4:44
  • $\begingroup$ @NoamD.Elkies: any range $(2-\epsilon)p<|P|\le 2p$ with $\epsilon>0$ fixed is fine for my purposes. $\endgroup$ – Seva May 2 '18 at 5:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Seva May 2 '18 at 5:41
  • $\begingroup$ And, BTW, why do you say "in the theorem of Redei"? Isn't it a theorem of Szonyi? $\endgroup$ – Seva May 2 '18 at 5:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Luca Ghidelli May 2 '18 at 13:01
  • 1
    $\begingroup$ 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"? $\endgroup$ – Seva Jun 5 '18 at 6:36
  • 1
    $\begingroup$ 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). $\endgroup$ – Seva Jun 6 '18 at 14:33

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.