# Constructing integer sets in which a certain equation has no solution

Given some linear equation, e.g., $$x+2y=3z+4u+5w,$$ I would like to construct a set $S$ of $n$ positive integers so that equation has no solution in $S$.

Two questions:

1) How big must the integers in $S$ be? That is, how large is $\max_{a \in S} a$? Can $S$ be chosen in such a way that this latter quantity is $O(n \log^k n)$ for some $k$?

2) How long does it take to construct (either deterministically or with randomization) a set $S$ of $n$ positive integers where a fixed linear equation has no solution, and such that the largest number $\max_{a \in S} a$ has (approximately) minimal size?

• Have you tried a random construction? Feb 6 '17 at 23:25
• What about equations like $x=y$? Feb 6 '17 at 23:29

Consider an equation $$\tag{E}a_1x_1+\dots+a_kx_k=0.$$ Let $s=\sum_ia_i$ be the sum of its coefficients.
If $s=0$, the equation (E) has solutions in every nonempty set $S$, hence you are out of luck.
If $s\ne0$, let $p$ be the smallest prime not dividing $s$. Note that $p=O(\log |s|)$. Then (E) has no solution such that $x_i\equiv1\pmod p$ for all $i=1,\dots,k$, hence the set $$S=\{1,p+1,\dots,(n-1)p+1\}$$ works, with maximum $(n-1)p+1$. For a fixed equation (E), this is $O(n)$, and the set can be computed as easily as it gets.
• The implied constant in $O(n)$ obtained by this method may not be optimal. For example, for the equation $x=3y$, we get the set of integers $u\equiv1\pmod3$ with maximum $\sim3n$. However, we could use the set of $u\equiv1,2\pmod3$ with maximum $\sim\frac32n$, or even the set of $u$ such that $v_3(u)$ is even, with maximum $\sim\frac43n$. Feb 7 '17 at 13:41
This has been studied in the case of the specific linear equation $$x + y = w + z$$ where (allowing trivial solutions such as $x=w, y=z$) the set $S$ is a Golomb ruler / Sidon set.
In this case, the answer to 1 is that $\max_{a \in S}a = \Theta(n^2)$, and the answer to 2 is that actually minimising the width of $S$ is unknown but speculated to be NP-hard; finding asymptotically optimal rulers is linear in $n$ using some geometric techniques.