<p>Consider an equation
$$\tag{E}a_1x_1+\dots+a_kx_k=0.$$
Let $s=\sum_ia_i$ be the sum of its coefficients.</p>

<p>If $s=0$, the equation (E) has solutions in every nonempty set $S$, hence you are out of luck.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-07T13:41:26.080Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2017-02-07T12:10:36.457Z
2017-02-07T12:10:36.457Z
Emil Jeřábek
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-07T09:31:46.527Z
2017-02-07T09:31:46.527Z
Peter Taylor
<p>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$.</p>

<p>Two questions:</p>

<p>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$? </p>

<p>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?</p>

CC BY-SA 3.0
2017-02-06T23:25:40.913Z
Have you tried a random construction?
Yuval Filmus
CC BY-SA 3.0
2017-02-06T23:29:35.343Z
What about equations like $x=y$?
Emil Jeřábek
<ds.algorithms>
Constructing integer sets in which a certain equation has no solution
Shiqu Z.
# Constructing integer sets in which a certain equation has no solution

(Asked by: username_0 on 2017-02-06)

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?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Have you tried a random construction?  
> **username_2**: What about equations like $x=y$?  

---

## 2 answers

### Answer by username_2 on 2017-02-07. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: 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$.  

---

### Answer by username_3 on 2017-02-07. Score: 0

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.


---

