4
$\begingroup$

A stapled sequence is defined as a set of consecutive positive integers such that no one of them is relatively prime with all of the others. When I first came across this definition, I thought it wouldn't be that difficult to find an $n\in \mathbb N$ such that every set $A=\{i\in\mathbb N: j≤i≤j+n-1\}$ for some $j\in \mathbb N$ is a stapled sequence.

It turned out, however, that it wasn't that trivial. I first tried to use the "identity" $$\text{gdc}(a,b)=\text{gcd}(a-bt,b)\;\;\forall a,b,t\in\mathbb N$$but it took me nowhere.

I then found an article which seemed to help; in the abstract of this article they assert, that there's a very simple proof to show that no stapled sequence containing $N$ consecutive positive intgers exist for any $N < 17$.

Nevertheless, I've tried to read the article and I don't find their proof trivial; I don't even understand it!

(It might be worth to tell that I'm a secondary school student interested in maths).

Could someone help me understand their proof or provide a own proof?

$\endgroup$
3
+50
$\begingroup$

I agree that the notations in the article are a little bit confusing and overkill if you're only interested in the result that there are no stapled sequences of length $\lt 17$. So here goes my simplified (but longer, because there are more details and explanations) presentation.

I say that two integers are friends if they are distinct and not coprime, and that they are $p$-friends (for a prime $p$) if they are distinct and both divisible by $p$. Thus, two integers are friends iff they are $p$-friends for some prime $p$, and a stapled sequence is a sequence in which everyone has a friend.

Lemma 3.6 (of the paper) If there is a stapled sequence of length $2N$, then

(a) there is also a stapled sequence of length $2N+1$.

(b) there is also a stapled sequence of length $2N-1$.

Proof of lemma 3.6 Let $S=(x+1,x+2,\ldots,x+2N)$ be a stapled sequence of length $2N$.

(a) Suppose first that $x$ is odd. Then I claim that $(x+1,x+2,\ldots,x+2N+1)$ is also stapled. Indeed, everyone except perhaps $x+2N+1$ already has a friend, and $x+2N+1$ is even and therefore a $2$-friend to $x+1$. A mirror argument shows that $(x,x+1,\ldots,x+2N)$ is stapled when $x$ is even.

(b) Suppose first that $x$ is odd. Then I claim that the follwing set is also stapled : $T=(x+1,x+2,\ldots,x+2N-1)$. To show this, we take a $y$ in $T$ and show that it has a friend in $T$. By hypothesis, $y$ has friend $z$ in $S$. If $z\neq x+2N$, then $z$ is already in $T$ and we are done. If $z=x+2N$, there is a prime $p$ that divides both $x+2N$ and $z$. If $p<N$, either $y-p$ or $y+p$ is in $T$ and is a $p$-friend of $y$, and we are done also. Finally, if $p\geq N$, then there are only two integers divisible by $p$ in $S$, namely $x+2N$ and $x+2N-p$. So $y=x+2N-p$ is even and has $2$-friends inside $T$, which finishes the proof that $T$ is stapled. A mirror argument shows that $(x+2,x+3,\ldots,x+2N)$ is stapled when $x$ is even.

Lemma 3.7 (of the paper) If there is a stapled sequence of length $p$ where $p$ is an odd prime, then there is also a stapled sequence of length $p+1$.

Proof of lemma 3.7 Let $S=(x+1,x+2,\ldots,x+p)$ be a stapled sequence of length $p$. By the Chinese remainder theorem, there is an $x'$ such that $x'$ is congruent to $x$ modulo every prime $<p$, and such that $x'+p+1$ is divisible by $p$. Then $x'+1$ and $x'+p+1$ are $p$-friends, and friends in $S=(x+1,x+2,\ldots,x+p)$ stay friends when translated by $x'-x$. Thus $S'=(x'+1,x'+2,\ldots,x'+p+1)$ is a stapled sequence.

Taking the contrapositive statements of lemmata 3.6 and 3.7, we obtain the following :

Corollary. Let $Z$ be the set of all integers $z$ such that there are no stapled sequences of length $z$. Then :

(R1) If $z\in Z$ is odd, then $z-1\in Z$ also.

(R2) If $z\in Z$ is such that $z-1$ is prime, then $z-1\in Z$ also.

(R3) If $z\in Z$ is odd, then $z+1\in Z$ also.

In particular, applying rules R1 and R2 alternatively one sees that if $15\in Z$, then all of $14,13,12,11,10$ are in $Z$ ; also $16\in Z$ by R3. Similarly, if $9\in Z$ then all of $8,7,6,5,4,3,2$ are in $Z$.

So, to show that there are no stapled sequences in length $\leq 16$, it suffices to show that there are no stapled sequences in length $9$ or $15$.

Theroem 3.8 (of the paper) There are no stapled sequences of length $\leq 16$.

Proof of theorem 3.8 from lemma. As noted above, it suffices to show that

(a) There are no stapled sequences in length $9$.

(b) There are no stapled sequences in length $15$.

(a) : Suppose that $S=(x+1,x+2, \ldots,x+9)$ is stapled. The set $Y=\lbrace x+1,x+3,x+5,x+7,x+9\rbrace$ contains at most two multiples of $3$, at most one multiple of $5$ and at most one multiple of $7$. So some $y\in Y$ is not divisible by any of $3,5,7$. We know that $y$ has a friend $z$ in $S$, so they are both divisible by a prime $p$. The only possibility is then $p=2$, so $x$ is odd. Next, consider $U=\lbrace x+2,x+4,x+6,x+8\rbrace$. This set contains at most one multiple of $5$ and at most one multiple of $7$, so there are two elements $u_1,u_2 \in U$ not divisible by $5$ or $7$. We know that $u_i(1\leq i \leq 2)$ has a friend $v_i$ in $S$, so they are both divisible by a prime $p_i$. The only possibility is then $p_i=3$ (for both values of $i$). So both $u_1$ and $u_2$ are divisible by $3$ ; but the only two elements congruent to each other modulo $3$ in $U$ are $x+2$ and $x+8$. It follows that $x\equiv 1[\mod 3]$. Combining the two congruences that we now have on $x$, we see that $x$ is of the form $6q+1$. But then $x+4=6q+5$ and $x+6=6q+7$, and one of those two numbers is not divisible by any of $2,3,5$, and therefore cannot have any friends in $S$.

(b) : Suppose that $S=(x+1,x+2, \ldots,x+15)$ is stapled.

Each element of $A(x)=\lbrace x+3,x+4,\ldots,x+13\rbrace$ has a friend in $S$ which is at at most $12$ of distance to it, and so must be divisible by a prime $\leq 12$.

Each element of $B(x)=\lbrace x+5,x+6,\ldots,x+11\rbrace$ has a friend in $S$ which is at at most $10$ of distance to it, and so must be divisible by a prime $\leq 10$.

Next, let $C(x)$ be set of all elements of $A(x)$ not divisible by $2$ or $3$. The content of $C(x)$ depends of the value of $x$ modulo $6$ :

$$ \begin{array}{|l|c|} \hline x \ (mod\ 6) & C(x) \\ \hline 0 & \lbrace x+5,x+7,x+11,x+13\rbrace \\ \hline 1 & \lbrace x+4,x+6,x+10,x+12\rbrace \\ \hline 2 & \lbrace x+3,x+5,x+9,x+11\rbrace \\ \hline 3 & \lbrace x+4,x+8,x+10\rbrace \\ \hline 4 & \lbrace x+3,x+7,x+9,x+13\rbrace \\ \hline 5 & \lbrace x+6,x+8,x+12,x+14\rbrace \\ \hline \end{array} $$

We see then that $x \ (mod\ 6)$ is not $3$ or $4$, then $C(x)$ is a set of four elements that are not congruent to each other modulo $5,7$ or $11$, so that one of them is not divisible by $5,7$ or $11$, which is impossible. So we can assume that $x \ (mod\ 6)$ is $3$ or $4$. Next, let $D(x)$ be set of all elements of $C(x)$ not divisible by $2$ or $3$. We have :

$$ \begin{array}{|l|c|} \hline x \ (mod\ 6) & D(x) \\ \hline 3 & \lbrace x+8,x+10\rbrace \\ \hline 4 & \lbrace x+5,x+9,x+11\rbrace \\ \hline \end{array} $$

Reasoning as before, we see that $x \equiv 4 (mod\ 6)$ is impossible. So we must have $x \equiv 3 (mod\ 6)$, and further, one of $x+8,x+10$ is divisible by $5$, and the other is divisible by $7$.

But then, in $C(x)=\lbrace x+4,x+8,x+10\rbrace$, the remaining $x+4$ is not divisible by $5$ or $7$ and so cannot have any friends in $S$. This finishes the proof.

$\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.