2
$\begingroup$

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?

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

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Feb 7 '17 at 13:41
0
$\begingroup$

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.

$\endgroup$

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.