7
$\begingroup$

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$:


Run9
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?

$\endgroup$
  • 1
    $\begingroup$ Incidentally, the density of composite points is $1 - \frac{1}{\zeta(2)} \approx 0.39$. See, e.g., Pete Clark's posting. $\endgroup$ – Joseph O'Rourke Dec 24 '16 at 18:25
  • 1
    $\begingroup$ Just curious: for a given pair $(a,b)$, it is possible to tell the maximal length of composites along the anti-diagonal line $(a+i,b-i)$? Surely, in terms of $a$ and $b$. $\endgroup$ – T. Amdeberhan Dec 25 '16 at 17:08
  • $\begingroup$ @T.Amdeberhan, not as well as I would like. See my answer regarding Jacobsthal's function. Gerhard "And Many Other MathOverflow Posts" Paseman, 2016.12.25. $\endgroup$ – Gerhard Paseman Dec 25 '16 at 22:07
10
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In fact, the graph above is a compilation of (characteristic functions of) nontotatives of integers n arranged anti-diagonally (read off the line x+y=n). It would be impressive if it could be used to predict analytically the locations of these long anti diagonal stretches. Gerhard "Especially For Even Omega Values" Paseman, 2016.12.25. $\endgroup$ – Gerhard Paseman Dec 25 '16 at 16:00
1
$\begingroup$

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.

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