¿Una conjetura de $\frac{1}{3}$?

Question

Pregunta: Vamos a $A(n)$ ser finito, plaza de $n \times n$ matriz con entradas de $a_{ij}=1$ si $i+j$ es un poder perfecto; de lo contrario equivale a $0$. Es cierto que el $${1 \por encima de 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij} \leq {1 \por encima de 1.5 pt 3}$$ con la celebración de igualdad si y sólo si $n=3$ o $n=6$ ?

Deje $A(n)$ ser finito, plaza de $n \times n$ matriz con entradas de $a_{ij}=1$ si $i+j$ es un poder perfecto; de lo contrario es igual a $0$. Por ejemplo veamos $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}$$

Podemos demostrar que ${1 \above 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij} \leq {1 \above 1.5pt 3}$ con la celebración de igualdad si y sólo si $n=3$ o $n=6$. El siguiente gráfico representa los valores de ${1 \above 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij}$ pequeña $n$. La gráfica es lo que me motivó a hacer la pregunta. Parece que los valores máximos se alcanzan si $n=3$ o $n=6$.

Aquí fue mi enfoque: Vamos a $^t$ ser la transposición de mapa en el que se envía a la entrada de $a_{ij} \to a_{ji}$. La conmutatividad de la suma nos muestra que si $i+j$ es un poder perfecto, entonces lo es $j+i$. Equivalentemente, podemos ver que $a_{ij}=a_{ji}$. En particular, $A(n)^t=A(n)$ $A(n)$ es simétrica. Ahora observe que el $(a_{ij})^2=a_{ij}$. Desde $A(n)$ es simétrica $A(n)^tA(n)=A(n)^2$. El siguiente resultado es fácil de demostrar $$\sum_{i=1}^n \sum_{j=1}^n a_{ij}=tr(A(n)^2)$$ Similarly it easy to show that if ${1 \por encima de 1.5 pt n^2}\sum_{i=1}^n \sum_{j=1}^n a_{ij}={1 \por encima de 1.5 pt x}$ then $x$ is a divisor of $n$. Assume ${tr(A(n)^2) \por encima de 1.5 pt n^2}={1 \por encima de 1.5 pt 3}$ then $3$ divides $n$. We start by showing via inspection the base case of $n=3$ and $n=6$. Suppose $n=3$

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

Y por lo $tr(A(3)^2)=3$. Seguramente ${3 \above 1.5pt 3^2}={1 \above 1.5 pt 3}$. Del mismo modo es fácil de calcular y mostrar que si $n=6$

$$(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}$$

Y a partir de esto podemos ver que $tr(A(6)^2)=12$. Y de nuevo tenemos que ${12 \above 1.5pt 6^2}={1 \above 1.5 pt 3}$.

Suponga $n\neq 3$$n\neq 6$. Ahora desde ${tr(A(n)^2) \above 1.5pt n^2}={1 \above 1.5pt 3}$ sabemos que $3\times tr(A(n)^2)=n^2$. Si $a_{ii}$ es cualquier entrada de la diagonal de a $A(n)^2$ luego explícitamente $3(a_{11}+ \ldots +a_{nn})=n^2$ $\sqrt{3}\sqrt{a_{11}+\ldots + a_{nn}}=n$ y, en consecuencia, $\sqrt{3} \mid \sqrt{a_{11}+\ldots + a_{nn}}$ lo contrario $n$ no es un número entero que es una contradicción.

^La actualización 1: El argumento de rayado de arriba está mal gracias a la comentarista de @SEWillB. ^Actualización 2: El argumento previamente rayado arriba es correcta. Ver ediciones.

Eso es todo lo que puede venir para arriba con - y podría no ser el mejor enfoque y, posiblemente, el problema es trivial, y estoy perdiendo. También podría estar equivocado. El cuadro siguiente proporciona algunos datos para valores pequeños de a $n$.

Answer 1

Como en @Winther comentario, me voy a centrar en la forma asintótica de la densidad de la perfecta poderes.

Para ser más específicos, la cantidad de perfecto poderes que no exceda el $n$$\alpha(n)$. Si podemos probar $\frac{\alpha(2m)}{m}<\frac{1}{3}$ todos los $m>N$, entonces tenemos que comprobar todos los $6<n\le N$ manualmente, ya podemos probar $$\frac{\alpha(2m)}{m}\ge{1 \above 1.5 pt m^2}\sum_{i=1}^m \sum_{j=1}^ma_{ij}$$

La prueba de la desigualdad anterior es simple. Ya existen en la mayoría de las $m$ soluciones a $i+j=k, 1\le i,j \le m$, un poder perfecto "contribuye" a la mayoría de las $m$ a la suma de $a_{ij}$s. De ello se desprende ${1/ m^2}\sum_{i=1}^m \sum_{j=1}^ma_{ij} \le (1/m^2) m\alpha(2m)=\alpha(2m)/m$.

Hay menos de $\sqrt{2n}$ números al cuadrado y $\sqrt[3]{2n}$ cúbicas de números que no es $1$ y no exceda el $2n$, e $\sqrt[5]{2n}$ 5-el poder de los números (tenga en cuenta que cada 4-el poder de los números también son cuadrados). También, desde la $2^{\log_2{2n}}=2n$, la categoría de poder números están a menos de $\log_2{2n}$. Por lo tanto, el número de perfecto poderes, que no es $1$ y no exceda el $2n$ es más: $$\sqrt{2n}+\sqrt[3]{2n}+(\log_2{2n}-4)\sqrt[5]{2n}$$ Y uno puede comprobar que este no exceda el $\frac{n}{3}$ si $n \ge 151$. Ahora uno puede comprobar manualmente la relación no exceda el $\frac{1}{3}$ pequeña $n$s con la excepción de $1$ $30$y la conclusión de la prueba.