16
$\begingroup$

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

$\endgroup$
16
  • 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, 2017 at 14:32
  • 1
    $\begingroup$ And In fact I think this kills your argument? $\endgroup$
    – SEWillB
    May 25, 2017 at 14:34
  • 1
    $\begingroup$ Ok I will post an answer in a minute $\endgroup$
    – SEWillB
    May 25, 2017 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, 2017 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, 2017 at 15:33

1 Answer 1

Reset to default
6
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .