Arbitrarily long composite anti-diagonals?

Question

Plot points $(a,b) \in \mathbb{N}^2$ if gcd$(a,b) \neq 1$. Call such points composite points. Call a sequence of points $(a+i,b-i), i=0,\ldots,k$ a composite anti-diagonal if all are composite points. For example, the points $$ (182, 148), (183, 147), (184, 146), (185, 145), (186, 144), (187, 143), (188, 142), (189, 141), (190, 140) $$ with gcd's $$ 2, 3, 2, 5, 6, 11, 2, 3, 10 $$ form a composite anti-diagonal of length $9$:

---

---

Just out of curiosity:

Are there arbitrarily long composite anti-diagonals?

I assume so. Can an example be constructed explicitly, i.e., an example with parameters whose length can be made arbitrarily long by appropriate choice of parameters?

Answer 1

Bit more explicit form of Seva's example is the following. Assume that both $a-2,b+2$ are divisible by all primes between 2 and $k+2$. Then $$gcd(a+i,b-i)=gcd((a-2)+i+2,b+2-(i+2))>1$$ for all $i=0,\dots,k$.

Answer 2

Fix integer $k\ge 1$, and let $p_i$ denote the $i$th prime. By the Chinese Remainder Theorem, there exist integer $a,b>k$ such that $a\equiv -i\pmod{p_i}$ and $b\equiv i\pmod{p_i}$ for each $i=1,\dotsc,k$. Now $p_i\mid\gcd(a+i,b-i)$ for $i=1,\dotsc, k$, which yields a length-$k$ antidiagonal.

In the same way one can show, say, that for any integers $x_1,\dotsc,z_k$ there exist (arbitrarily large) integers $a,b,c$ such that $\gcd(a+x_i,b+y_i,c+z_i)>1$ for each $i\in[1,k]$.

Answer 3

If you're not into "hunting for primes", here is a slight and concrete variant.

Let $a-2=(k+2)!$ and $b+2=(k+2)!$. Then proceed in the same manner as Fedor's example: for $0\leq i\leq k\geq2$, we have $$\text{gcd}(a+i,b-i)=i+2>1.$$

BTW, very cool drawing, Joseph!

Answer 4

I just have to add a Jacobsthal mention. For any composite $n \gt 1$, there is a natural anti-diagonal formed by $(a+i,n-(a+i))$ where $a$ is the lower boundary of an interval of $g(n)$-many numbers, with $i=0$ representing two numbers with gcd being 1, and $i$ up to $g(n)-1$ being a nontrivial divisor of $n$. One can take n=2310, a=113, and g(n) is 14. More recent examples have appeared on ArXiv within the last couple of months. Of course, Joseph is looking for any such long intervals of i yielding (a+i,b-i), whose gcd is a factor of a+b.

Gerhard "Should See These Things Coming" Paseman, 2016.12.24.

Answer 5

I've decided to take some research off the back burner and share it here, as it addresses a slight generalization of Joseph's question.

Rephrasing Seva's answer , take as many distinct primes $p_i$ as you wish, call their product $a+b$, and solve for $a$ using the congruences $a+i \equiv 0 \mod p_i$. If you want the same size $a+b$, but a longer interval, you need to replace $a+i$ with $a+h(i)$, where some effort has been exerted to find these offsets $h(i)$. (See Hagedorn's 2009 paper and later for more; he uses $h(n)$ to mean something different.) The effort is related to Jacobsthal's function , on which I posted a question in 2010 (cf MathOverflow 37679).

What if you wanted to find many of these diagonals with the same value for $a+b$? A quick way is to permute the $i$'s: if there are $k$ primes, there may be up to $k!$ many choices for $a$. However, inverting a system of congruences a factorial number of times is tedious. Is there a better way?

I spent some time in 2014 thinking of a better way, and found this interesting bit. Let the $k$ distinct primes all be greater than $k$. If $k$ is odd, there is a correspondence between these $k!$ intervals and additive permutations, so that some pairs of the intervals add to give other intervals. As an example, 98,99,100 and 20,21,22 add to give 119,120,121 for $k=3$. Further, this implies that some of these intervals are "far away" from the $x=y$ diagonal.

More interesting is the fact that this breaks horribly for even $k$. Not only is there no such nice additive relation between any of the intervals, but some numbers $n$ seem to have all their $k!$ many intervals grouped near the main diagonal, as opposed to having them spread far apart as in the odd $k$ situation. I will spend some time this coming year thinking about these narrow numbers $n$, and I now invite others to do so and share their thoughts.

Gerhard "Can Be Narrow And Sharing" Paseman, 2016.12.26.