$F$-Diophantine sets over finite fields

A set of $m$ positive integers is a Diophantine $m$-tuple if the product of any two distinct elements in the set is one less than a perfect square. There are many interesting results in the study of Diophantine tuples and their variants. Perhaps most notable is the Diophantine quintuple conjecture, namely, there is no Diophantine quintuple, recently confirmed by He, Togbé, and Ziegler [11]. We refer to the Dujella’s book [5] for a comprehensive discussion on the topic and their reference.

The definition of $F$-Diophantine sets were formally introduced by Bérczes, Dujella, Hajdu, Tengely [1] for a polynomial $F\in{\mathbb{Z}}[x,y]$. Given a polynomial $F\in{\mathbb{Z}}[x,y]$, they say that a subset $A$ of integers is an $F$-Diophantine set if $F(x,y)$ is a perfect square for all $x,y\in A$ with $x\neq y$. $F$-Diophantine sets naturally appear in various contexts and are related to many interesting problems in number theory. In particular, an $F$-Diophantine set with $F(x,y)=xy+n$ and $n\neq 0$ corresponds to a Diophantine tuple with property $D(n)$ (see for example [4]). Similar to the study of classical Diophantine tuples, it is of special interest to construct large $F$-Diophantine sets or give bounds on the maximum size of $F$-Diophantine sets [1, 16].

In this paper, we study the natural analogue of $F$-Diophantine sets over finite fields. Throughout the paper, let $q$ be an odd prime power, ${\mathbb{F}}_{q}$ the finite field with $q$ elements, and ${\mathbb{F}}_{q}^{*}={\mathbb{F}}_{q}\setminus\{0\}$. Let $k\geq 2$ and $F\in{\mathbb{F}}_{q}[x_{1},\ldots,x_{k}]$ be a polynomial. We say $A\subset{\mathbb{F}}_{q}^{*}$ is an $F$-Diophantine set over ${\mathbb{F}}_{q}$ if $F(a_{1},a_{2},\ldots,a_{k})$ is a square in ${\mathbb{F}}_{q}$ whenever $a_{1},a_{2},\ldots,a_{k}$ are distinct elements in $A$. In the same spirit, we are interested in estimating the quantity $M(F;{\mathbb{F}}_{q})$, the maximum size of $F$-Diophantine sets over ${\mathbb{F}}_{q}$¹¹1The definition of $M(F;{\mathbb{F}}_{q})$ still makes sense when $q$ is even, however in that case we trivially have $M(F;{\mathbb{F}}_{q})=q-1$ since each element in ${\mathbb{F}}_{q}$ is a square.. Although such terminology appears to be new in general, for many special polynomials $F$, $F$-Diophantine sets over finite fields have been studied extensively in different contexts. The obvious choice $F(x,y)=xy+\lambda$ with $\lambda\in{\mathbb{F}}_{q}^{*}$ corresponds to generalized Diophantine tuples over ${\mathbb{F}}_{q}$ [6, 9, 12, 14, 17, 18]. $F$-Diophantine sets over ${\mathbb{F}}_{q}$ with $F(x,y)=x-y$ (when $q\equiv 1\pmod{4}$) corresponds to cliques in the Paley graph over ${\mathbb{F}}_{q}$. In the aforementioned two cases, when $q$ is a non-square, we have the “trivial” bounds

see [12, 13, 19]. However, any bound beyond the above requires highly non-trivial efforts. We refer to [3, 12, 14, 13, 19, 20] for recent multiplicative constant improvement on the lower bounds and upper bounds from polynomial methods, finite geometry, number theory, and graph theory. Moreover, when $k=2$, the authors [13] have studied lower bounds and upper bounds on $M(F;{\mathbb{F}}_{q})$ for a generic polynomial $F\in{\mathbb{F}}_{q}[x,y]$. We focus on the case $k\geq 3$ in this paper.

Next we discuss lower bounds and upper bounds on $M(F;{\mathbb{F}}_{q})$ for a generic polynomial $F\in{\mathbb{F}}_{q}[x_{1},x_{2},\ldots,x_{k}]$ with degree $d$. From [13, Section 3.3], one can deduce that $M(F;{\mathbb{F}}_{q})=O_{d}(\sqrt{q})$ if $F$ is generic. Note that this upper bound is sometimes sharp. Indeed, if $q$ is a square and $F$ is defined over ${\mathbb{F}}_{\sqrt{q}}$, then $A={\mathbb{F}}_{\sqrt{q}}^{*}$ is an $F$-Diophantine set over ${\mathbb{F}}_{q}$ since all elements in ${\mathbb{F}}_{\sqrt{q}}$ are squares in ${\mathbb{F}}_{q}$. Regarding the lower bound on $M(F;{\mathbb{F}}_{q})$, it is helpful to use a probabilistic heuristic. Assuming that the set of squares in ${\mathbb{F}}_{q}$ was a random subset of ${\mathbb{F}}_{q}$ with density $1/2$, then we expect that there exists an $F$-Diophantine set over ${\mathbb{F}}_{q}$ with size $n$ provided that

This suggests the heuristic lower bound that

Here, for two functions $f$ and $g$, $f=\Theta(g)$ means that both $f=O(g)$ and $g=O(f)$ are satisfied. Indeed, when $F(x_{1},x_{2},\ldots,x_{k})=x_{1}x_{2}\cdots x_{k}+1$, Hammonds, Kim, Miller, Nigam, Onghai, Saikia, and Sharma [10, Theorem 1.3] confirmed inequality (1.1) (they only considered the case where $q$ is an odd prime, but the same proof extends to all odd prime powers $q$). Unsurprisingly, in their terminology, such an $F$-Diophantine set over ${\mathbb{F}}_{q}$ is a $k$-Diophantine tuple over ${\mathbb{F}}_{q}$.

Before stating our main result, we need to introduce a new definition. We define a partial order on non-constant monic monomials in ${\mathbb{F}}_{q}[x_{1},x_{2},\ldots,x_{k}]$. Let $f=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{k}^{\alpha_{k}}$ and $g=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{k}^{\beta_{k}}$, where $\alpha_{1},\beta_{1},\ldots,\alpha_{k},\beta_{k}$ are nonnegative integers. We write $f\succeq g$ if $\alpha_{i}\geq\beta_{i}$ for each $1\leq i\leq k$, and write $f\succ g$ if $f\succeq g$ and $f\neq g$. Let $F\in{\mathbb{F}}_{q}[x_{1},x_{2},\ldots,x_{k}]$ be a nonzero polynomial. We can write $F$ in its monomial expansion as follows:

where each $a_{i}\in{\mathbb{F}}_{q}^{*}$, $f_{i}$ is a monomial of degree at least $1$, and $C\in{\mathbb{F}}_{q}$. We say $F$ is of type I if $C$ is a non-zero square in ${\mathbb{F}}_{q}$. We say $F$ is of type II if there is $1\leq i\leq m$, such that $a_{i}$ is a square in ${\mathbb{F}}_{q}^{*}$, and $f_{i}\succ f_{j}$ for all $1\leq j\leq m$ with $j\neq i$.

Applying Theorem 1.1 to $F(x_{1},x_{2},\ldots,x_{k})=x_{1}x_{2}\ldots x_{k}+1$ (which is of both type I and type II), we get the following corollary immediately. In particular, it significantly improves the lower bound $\Theta((\log q)^{1/(k-1)})$ on the maximum size of $k$-Diophantine tuples over ${\mathbb{F}}_{q}$ by Hammonds et. al [10].

Interestingly, our approach provides a substantial improvement on the heuristic lower bound of $M(F;{\mathbb{F}}_{q})$ given in inequality (1.1), whenever $k\geq 3$ and $F\in{\mathbb{F}}_{q}[x_{1},x_{2},\ldots,x_{k}]$ is a sparse polynomial. The constant factors in Theorem 1.1 and Corollary 1.2 are not optimal. Here we focus on improving the order of the magnitude of the lower bound and we do not attempt to optimize the constant factors. On the other hand, in the case $k=2$, improving the constant factors in front of $\log q$ is of special interest; see [13] and references therein for more discussions.

Let $q$ be an odd prime power. Let $F\in{\mathbb{F}}_{q}[x_{1},x_{2},\ldots,x_{k}]$ be a polynomial of type I or type II, with degree $d$. Write $F$ in its monomial expansion as follows:

where $a_{i}\in{\mathbb{F}}_{q}^{*}$ and $f_{i}$ is a monomial of degree at least $1$ for each $1\leq i\leq m$, and $C\in{\mathbb{F}}_{q}$.

Let $n$ be a positive integer to be determined such that $2\leq n\leq q^{1/4}$. Consider the following collection of polynomials in ${\mathbb{F}}_{q}[x]$:

Observe that

Also, if $F$ is of type I, then the constant term of each polynomial $g\in V$ is a non-zero square in ${\mathbb{F}}_{q}$; if $F$ is of type II, then the leading coefficient of each polynomial $g\in V$ is a non-zero square in ${\mathbb{F}}_{q}$. In both cases, it readily follows that the product of polynomials in any subset of $V$ is not of the form $ch^{2}$, where $c$ is a non-square in ${\mathbb{F}}_{q}$, and $h$ is a polynomial in ${\mathbb{F}}_{q}[x]$.

Let $Y$ denote the collection of $y\in{\mathbb{F}}_{q}^{*}$ with order at least $n$, such that the set $\{g(y):g\in V\}$ is contained in the set of squares in ${\mathbb{F}}_{q}$. Let $N=|Y|$ and let $\chi$ be the quadratic character in ${\mathbb{F}}_{q}$. We claim that

Indeed, if $y\notin Y$, then $g(y)$ is a non-square in ${\mathbb{F}}_{q}$ for some $g\in V$, and thus such $y$ does not contribute to the right-hand side of inequality (2.2). On the other hand, if $y\in Y$, then $\chi(g(y))\in\{0,1\}$ for each $g\in V$, and thus it contributes at most $1$ to the right-hand side of inequality (2.2).

Expanding the product on the right-hand side of inequality (2.2) yields

where $Z=\{0\}\cup\{y\in{\mathbb{F}}_{q}^{*}:\operatorname{ord}y<n\}$. Since ${\mathbb{F}}_{q}^{*}$ is a cyclic group, it is clear that $|Z|\leq n^{2}$.

We need to use Weil’s bound for complete character sums (see for example [15, Theorem 5.41]), which we recall below.

We have mentioned that for each subset $W$ of $V$, the product $\prod_{g\in W}g$ is not of the form $ch^{2}$, where $c$ is a non-square in ${\mathbb{F}}_{q}$, and $h$ is a polynomial in ${\mathbb{F}}_{q}[x]$. Therefore, separating the contribution from $W=\emptyset$ and $W\neq\emptyset$, and applying Weil’s bound, we further deduce that

Given inclusion (2.1), $\deg(g)\leq dn$ for each $g\in V$. Thus, a simple double-counting argument shows that

We conclude from the assumption $n\leq q^{1/4}$, inequality (2.3) and inequality (2.4) that

Note that $|V|\leq(dn)^{m}$ from inclusion (2.1), thus

Since $q\geq 257$, we have $\log_{4}q>4\log_{4}\log_{4}q$. Set

Then we have $(dn)^{m}\leq\log_{4}q-4\log_{4}\log_{4}q$ and thus

It follows from inequality (2.5) that

Note that $N>0$ implies that $N\geq 1$, that is, there exists $y_{0}\in{\mathbb{F}}_{q}^{*}$ with order at least $n$, such that the set $\{g(y_{0}):g\in V\}$ is contained in the set of squares in ${\mathbb{F}}_{q}$. Let

then $A$ is an $F$-Diophantine set over ${\mathbb{F}}_{q}$ with $|A|=n$. This proves Theorem 1.1, as required.

Next, we give several remarks on our constructions.

The second author was supported by the Institute for Basic Science (IBS-R029-C1). The authors thank Seoyoung Kim for helpful discussions. The authors are also grateful to anonymous referees for their valuable comments and corrections.