Multiplicatively irreducibility of small perturbations of shifted $k$-th powers

Let $\mathbb{N}$ be the set of positive integers. In this paper, we study questions related to additive decompositions and multiplicative decompositions. A set $S\subset\mathbb{N}$ is said to be multiplicatively reducible if it has a multiplicative decomposition $S=AB=\{ab:a\in A,b\in B\}$, where $A,B$ are subsets of $\mathbb{N}$ with size at least $2$. Similarly, $S$ is additively reducible if it can be written as a sumset $A+B=\{a+b:a\in A,b\in B\}$, where $A,B$ are subset of $\mathbb{N}$ with size at least $2$. There is a large amount of literature on the study of additive dnd multiplicative decompositions for sets with different arithmetic structures; we refer to a nice survey by Elsholtz [7].

The set of perfect squares is additively irreducible simply because the gap between consecutive squares tends to infinity. Erdős conjectured that all small perturbations of the set of squares are still additively irreducible.

This conjecture is still open, with the best-known progress due to Sárközy and Szemerédi [18], where they showed that 1.1 holds if one replaces $o(X^{1/2})$ with $o(X^{1/2}/2^{(3+\epsilon)\log X/\log\log X})$ for any $\epsilon>0$. We also refer to related results by Bienvenu [2] and Leonetti [15] with a probabilistic flavor. It appears that the finite field analogue of 1.1 is even more challenging (if true); we refer to [12, 16, 19, 21] for some partial results.

Recently, Hajdu and Sárközy studied the multiplicative decompositions of polynomial sequences with integer coefficients in a series of three papers [9, 10, 11]. In particular, in the first two papers, they provided a simple proof of the following result: for each $k\geq 2$, if one changes finitely many elements of the set $M_{k}^{\prime}=\{x^{k}+1:x\in\mathbb{N}\}$, then the new set remains multiplicatively irreducible. We also refer to the study of finite field analogues of the same result in [13, 17].

In the third paper of the series [11], Hajdu and Sárközy studied the following multiplicative analogue of 1.1.

1.2 is best possible in the sense that if one changes a positive proportion of elements from $\{x^{k}+1:x\in\mathbb{N}\}$ (equivalently, changes at most $cX^{1/k}$ elements of the set $\{x^{k}+1:x\in\mathbb{N}\}$ up to $X$ for some constant $c>0$), then the resulting set could be multiplicatively reducible. For example, let $m\geq 2$ be an integer and set $R_{m}=AB$, where $A=\{1,m\}$ and $B=\{x^{k}+1:x\in\mathbb{N}\}$; note that $R_{m}$ is obtained by adding $(m^{-1/k}+o(1))X^{k}$ elements to $\{x^{k}+1:x\in\mathbb{N}\}$ up to $X$ and $m^{-1/k}\to 0$ as $m\to\infty$.

Based on a skillful and sophisticated argument involving various tools from Diophantine approximation, Diophantine equations, extremal graph theory, and multiplicative number theory, Hajdu and Sárközy [11, Theorem 2.1] proved a weaker version of 1.2. More precisely, they proved that 1.2 holds if $o(X^{1/k})$ is replaced by

for any $\epsilon>0$. They remarked that both 1.1 and 1.2 “seem to be beyond reach in their original form”.

In this paper, we prove a more general version of 1.2 for $k\geq 3$.

One key ingredient in our proof is the connection of multiplicative decompositions of the set $M_{k}^{\prime}$ and the bipartite variants of Diophantine tuples, first considered by the author [20] as an attempt to make some of the results in [9, 10] effective. There are many well-studied generalizations and variants of Diophantine tuples; see the recent book of Dujella [6] for an overview. The relevant variant in our setting is the following bipartite variant: for each $k\geq 2$ and each nonzero integer $n$, we call a pair of sets $(A,B)$ a bipartite Diophantine tuple with property $BD_{k}(n)$, if $A,B$ are two subsets of $\mathbb{N}$ with size at least $2$, such that $ab+n$ is a $k$-th power for each $a\in A$ and $b\in B$. While this concept was only formally introduced by the author [20] recently, the same objects have been for example studied by Gyarmati [8], Bugeaud and Dujella [3], and Bugeaud and Gyarmati [4], since two decades ago. The connection is the following: if we can give a good absolute upper bound on $\min\{|A|,|B|\}$ among all bipartite Diophantine tuples $(A,B)$ with property $BD_{k}(n)$, then it seems plausible that the following Kövari–Sós–Turán theorem [14] from extremal graph theory can be used to make some partial progress on 1.2.

Our proof techniques cannot handle the case $k=2$ in 1.2. In fact, it is an open question to show unconditionally that if $(A,B)$ is a bipartite Diophantine tuple with property $BD_{2}(1)$, then $\min\{|A|,|B|\}$ is bounded by an absolute constant [1, 4]; note that this would follow easily if we assume the uniformity conjecture [5]. As for the case for $k\geq 3$, the same question was partially addressed by the author [20]; in particular, it was shown in [20, Theorem 2.2] that if $k\geq 3$ is fixed, and $|n|\to\infty$, then for any bipartite Diophantine tuple $(A,B)$ with property $BD_{k}(n)$, we have $\min\{|A|,|B|\}\ll_{k}\log|n|$. Clearly, such a result is not strong enough for the application to 1.2. Instead, we realize that studying a “local version” of bipartite Diophantine tuples is sufficient to prove 1.2 for $k\geq 3$.

In this section, we prove some refined “local estimates” on bipartite Diophantine tuples with some carefully chosen parameters. We list several results from [20] and deduce some useful corollaries. We first introduce the following constants defined in [20]:

The following proposition is one of the key results in [20]. Its proof is based on a combination of an explicit version of the bounds of the number of solutions of Thue inequalities, repeated applications of gap principles, and some combinatorial arguments.

For our purpose, we shall use the following immediate corollary of Proposition 2.1. Note that $t_{k}\leq 17$ and $s_{k}\leq 6$ for all $k\geq 3$.

The following lemma is based on a simple gap principle.

Next, we deduce two corollaries of 2.3.

Our proof is inspired by several arguments used in [11, 20]. In the following, we use the following standard notation: for each set $A\subset\mathbb{N}$ and each positive real number $X$, we write $A(X)=|\{x\in A:x\leq X\}|$.

The author thanks Ernie Croot, Greg Martin, and Jiaxi Nie for helpful discussions.