Question: 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$. Is it true that $${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$ ?

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$. For an example consider $A(5)$

$$A(5)= \text{ }\begin{pmatrix} 0&0&1&0&0\\ 0&1&0&0&0\\ 1&0&0&0&1\\ 0&0&0&1&1\\ 0&0&1&1&0\\ \end{pmatrix}$$

Can we show that ${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$. The graph below plots the values of ${1 \above 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij}$ for small $n$. The graph is what motivated me to ask the question. It appears that the maximums are achieved if $n=3$ or $n=6$.

UPDATE: I have corrected several terms and added several new terms check out: A293462.

enter image description here

Here was my approach: Let $^t$ be the transpose map that sends the entry $a_{ij} \to a_{ji}$. The commutativity of addition shows us that if $i+j$ is a perfect power then so is $j+i$. Equivalently we see that $a_{ij}=a_{ji}$. In particular $A(n)^t=A(n)$ and so $A(n)$ is symmetric. Now observe that $(a_{ij})^2=a_{ij}$. Since $A(n)$ is symmetric $A(n)^tA(n)=A(n)^2$. The following result is easy to show $$\sum_{i=1}^n \sum_{j=1}^n a_{ij}=tr(A(n)^2)$$ Similarly it easy to show that if ${1 \above 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij}={1 \above 1.5 pt x}$ then $x$ is a divisor of $n$. Assume ${tr(A(n)^2) \above 1.5pt n^2}={1 \above 1.5pt 3}$ then $3$ divides $n$. We start by showing via inspection the base case of $n=3$ and $n=6$. Suppose $n=3$ then

$$A(3)^2= \text{ } \begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\\ \end{pmatrix}$$

And so $tr(A(3)^2)=3$. Surely ${3 \above 1.5pt 3^2}={1 \above 1.5 pt 3}$. Similarly it is easy to compute and show that if $n=6$

$$A(6)^2= \text{ }\begin{pmatrix} 1&0&0&0&1&1\\ 0&2&1&0&0&1\\ 0&1&3&1&0&0\\ 0&0&1&2&1&0\\ 1&0&0&1&2&1\\ 1&1&0&0&1&2\\ \end{pmatrix} $$

And from this we can see that $tr(A(6)^2)=12$. And again we have that ${12 \above 1.5pt 6^2}={1 \above 1.5 pt 3}$.

Assume $n\neq 3$ and $n\neq 6$. Now since ${tr(A(n)^2) \above 1.5pt n^2}={1 \above 1.5pt 3}$ we know that $3\times tr(A(n)^2)=n^2$. If $a_{ii}$ is any entry on the diagonal of $A(n)^2$ then explictly $3(a_{11}+ \ldots +a_{nn})=n^2$ so $\sqrt{3}\sqrt{a_{11}+\ldots + a_{nn}}=n$ and consequently $\sqrt{3} \mid \sqrt{a_{11}+\ldots + a_{nn}}$ otherwise $n$ is not an integer which is a contradiction.

^Update 1: The argument scratched out above is wrong thanks to commentator @SEWillB. ^Update 2: The argument previously scratched out above is correct. See edits.

That is all I can come up with - and it might not be the best approach and possibly the problem is trivial and I am just missing it. It could also be wrong. The picture below provides some data for small values of $n$.

  • 1
    $\begingroup$ I think that there are points where you've raised a trace to a power $tr(A)^2$ and you mean $tr(A^2)$ $\endgroup$ – SEWillB May 25 '17 at 14:32
  • 1
    $\begingroup$ And In fact I think this kills your argument? $\endgroup$ – SEWillB May 25 '17 at 14:34
  • 1
    $\begingroup$ Ok I will post an answer in a minute $\endgroup$ – SEWillB May 25 '17 at 14:42
  • 1
    $\begingroup$ Another way is to simply count how many $1$'s you have directly. There are $\lfloor\sqrt{2n}\rfloor$ perfect squares you can write as a sum $i+j$ with $i,j\in[1,n]$. For each such square $p^2$ there are $p^2-1$ different ways of writing it as $i+j$ (but not all of these are in your matrix). This gives that your sum is bounded above by something like $$\frac{1}{n^2}\sum_{p=1}^{\lfloor\sqrt{2n}\rfloor} p^2-1 \lesssim \frac{5}{4\sqrt{n}}$$ $\endgroup$ – Winther May 25 '17 at 15:17
  • 1
    $\begingroup$ Ok; my only thought so far is to use the generalisation of Catalan's conjecture (see Wikipedia page, generalisation where {n and n+1} or {n and n+2} can be perfect powers.) This was proved in 2002- so very difficult. But it will give a nice way of knowing what gets added to the matrix inductively as n increases $\endgroup$ – SEWillB May 25 '17 at 15:33

As in @Winther's comment, I will focus on the asymptotic density of perfect powers.

To be specific, let the number of perfect powers which does not exceed $n$ be $\alpha(n)$. If we can prove $\frac{\alpha(2m)}{m}<\frac{1}{3}$ for all $m>N$, then we need to check all $6<n\le N$ manually since we can prove $$\frac{\alpha(2m)}{m}\ge{1 \above 1.5 pt m^2}\sum_{i=1}^m \sum_{j=1}^ma_{ij}$$

The proof of above inequality is simple. Since there are at most $m$ solutions to $i+j=k, 1\le i,j \le m$, one perfect power "contributes" at most $m$ to the sum of $a_{ij}$s. It follows ${1/ m^2}\sum_{i=1}^m \sum_{j=1}^ma_{ij} \le (1/m^2) m\alpha(2m)=\alpha(2m)/m$.

There are less than $\sqrt{2n}$ square numbers and $\sqrt[3]{2n}$ cubic numbers which is not $1$ and does not exceed $2n$, and $\sqrt[5]{2n}$ 5-power numbers (note that every 4-power numbers are also squares). Also, since $2^{\log_2{2n}}=2n$, the category of power numbers are less than $\log_2{2n}$. Therefore, the number of perfect powers which is not $1$ and does not exceed $2n$ is at most:$$\sqrt{2n}+\sqrt[3]{2n}+(\log_2{2n}-4)\sqrt[5]{2n}$$ And one can check that this does not exceed $\frac{n}{3}$ if $n \ge 151$. Now one can manually check the ratio does not exceed $\frac{1}{3}$ for small $n$s except $1$ to $30$ and conclude the proof.


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.