9
$\begingroup$

A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the grid $A\times B$, then $\deg P\ge |A|+|B|-2$.

Can one improve this bound given that $P$ is homogeneous?

What is the smallest possible degree of a homogeneous polynomial $P(x,y)$ vanishing on all, but exactly one point of the grid $A\times B$?

The underlying field $\mathbb F$ can be assumed to have characteristic $2$.

$\endgroup$

2 Answers 2

3
$\begingroup$

In general homogeneity does not improve the bound. Take $A=\{1,q,q^2,\ldots,q^{a-1}\}$, $B=\{1,q,q^2,\ldots,q^{b-1}\}$, $f(x,y)=\prod_{i=-(b-1)}^{a-2}(x-q^iy)$.

$\endgroup$
3
$\begingroup$

If $0\notin B$, then $$F(x,y) = y^n \left(c_n \left(\frac{x}{y}\right)^n+\cdots+c_0\right).$$ Let $S=\{x/y:\ x\in A,y\in B\}.$ For $F$ to vanish on all the points of $A\times B$ except $1$, we must have that the one variable polynomial $$P(z)=c_n z^n+\cdots +c_0$$ vanishes on all the points of $S$ except $1$, and so $\deg F \geq |S|-1$.

In general, the Scherk-Kemperman Theorem states that $$|S|\geq |A|+|B|-\min_{c \in S}|A\cap cB|$$ (thank you Fedor for pointing this out) and equality is obtained if $A$ and $B$ are geometric progressions. Hence we will not have an improvement to the bound in the specific case where $A$ and $B$ are geometric progressions.

$\endgroup$
2
  • 1
    $\begingroup$ We do not always have $|S|\geqslant |A|+|B|-1$ for arbitrary $A, B$. But we do if a certain element in $S$ has unique representation as $a/b$ for $a\in A, b\in B$ (this is a theorem of Kemperman and Scherk), and this is exactly our case. $\endgroup$ Jun 4, 2022 at 19:28
  • $\begingroup$ @FedorPetrov Thank you, I've updated the answer with the statement of the Scherk-Kemperman Theorem $\endgroup$ Jun 4, 2022 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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