Equivalence between a limit and Pillai's Conjecture

Question

I have rewritten this problem entirely please see the edits:

On the MSE I asked the following conjecture:

* The ${1\above 1.5 pt 3}$ Conjecture:* Let $A(n)$ be a finite square $n \times n$ matrix with entries $a_{ij}=1$ if $i+j$ is a perfect power; otherwise equals to $0$. Then $${1 \above 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij} \leq {1 \above 1.5pt 3}$$ with equality holding if and only if $n=3$ or $n=6$ .

A commentator provided an answer to this conjecture and it appears correct. For short handedness I write $\xi(n)=n^{-2}\sum_{i=1}^n\sum_{j=1}^n a_{ij}$. Let $S_j$ be the $j$-th skew diagonal of $A(n)$. I say that $S_j$ is perfect if every entry is equal to $1$. The distance ( or "gap" counted in rows) between two perfect skews $S_j$ and $S_{j'}$ is denoted $K$. Let $x,y,m,n \in \mathbb{N}$. Consider the Diophantine equation $$x^n-y^m=K$$ with $m,n \neq 2$. Pillai conjectured that there are at most finitely many terms $\left(x,y,m,n\right)$ with $m,n \neq 2$ such that $x^n-y^m=K$. That is each positive integer occurs only finitely many times as a difference of perfect powers.

I believe I have a correct proof of a lemma which states a trivially obvious connection between Pillai's conjecture and the distance between any two perfect skews of $A(n)$.

lemma 1: Pillai's Conjecture is true if and only if each positive integer occurs finitely many times as the distance between two perfect skews.

proof (sufficiency): Suppose that Pillai's conjecture is true and each positive integer occurs infinitely many times as the distance between to perfect skews. Let $F_K$ be the family of perfect skews such that any two perfect skews in $F_K$ have distance equal to $K.$ By assumption $\left |F_K\right|=\infty$, so we can find infinitely many pair of matrix entries, say $a_{m,1}$ and $a_{m',1}$ in $A(n)$ such that:

• $a_{m,1}=1$ and $a_{m',1}=1$
• $m+1$ and $m'+1$ are perfect powers
• $K=|m-m'|$

Equivalently $K$ occurs infinitely many times as the difference between two perfect powers a contradiction since we assumed Pillai's conjecture is true.

proof (necessity): Suppose each positive integer occurs finitely many times as the distance between two perfect skews and Pillai's conjecture is false. Consider the family $F$ of perfect skews in $A(n)$ with pairwise distance equal to $K$. Let $F_K$ be the family of perfect powers such that any two perfect powers in $F_K$ differ by $K$. We must have $\left|F_K\right|=\left | F \right|$. Note $\left|F\right|$ is finite by supposition and so $\left | F_K \right|$ is finite; a contradiction. So the supposition that Pillai's conjecture is false, is false.

From the lemma I would like to think that Pillai's conjecture comes down to understanding the limit behaviour of $\xi(n)$ and so the following question is reasonable:

Question: Is it true that each positive integer occurs finitely many times as the distance between two perfect skews if and only if the $\lim_{n\to \infty}\xi(n)=0$ ?

The truthfulness of the above question combined with the lemma tells us that

$$\text{Pillai's Conjecture is true} \iff \lim_{n\to \infty}\xi(n)=0$$

Answer 1

I copy here my comment from the OEIS because StackExchange is a more convenient place for discussion.

$\xi(n)\to0$ as $n\to\infty$ is true because, as a comment in A001597 says, the sequence of perfect powers are asymptotic to $n^2$, so their density is asymptotic to $\sqrt{n}$ (see also didgogns's answer to your previous question), so at most $n\cdot\sqrt{n}=n^{3/2}$ entries are nonzero, and $n^{3/2}/n^2 = 1/\sqrt{n} \to 0$.

However, I don't see how it implies Pillai's conjecture. Indeed, consider the family of matrices $B(n)$ which are like $A(n)$ but skew diagonals with $i+j-1$ being perfect power are filled with 1's, too. This approximately doubles the number of 1's (this estimate can be made rigorous) and thus does not influence the validity of the analog of the statement "$\xi(n)\to0$ as $n\to\infty$" for $B(n)$, but the analog of Pillai's conjecture is false for $B(n)$. So Pillai's conjecture and the asymptotic behavior of $\xi(n)$ seem unrelated.