5
$\begingroup$

Question: Let $A(n)$ be a finite square $n \times n$ matrix with entries $a_{ij}=1$ if $i+j$ is a prime; otherwise equals to $0$. I write $|A(n)|$ to count the number of $1$'s in $A(n)$. Is it true, possibly trivially, and how can we show that

$$\lim_{n\to \infty}{|A_{n}|+|A_{n-2}| \above 1.5pt |A_{n-1}|}=2$$

The sequence of $A(n)$'s can be found here in Sloan. The graph below illustrates the limit. I believe I have shown the question is true, conditionally using a parity argument along with Bertrand's Postulate.

enter image description here

Solution:

It is easy to verify that $A(n)$ has exactly $2n-1$ skew diagonal. Two small lemmas.

$\underline{\text{lemma 1}}:$ Observe $a_{ii}=1$ if and only if $i=1$. Consequently $a_{11}$ is the only entry on the main diagonal of $A(n)$ equal to $1$. Note $A(n)$ is symmetric since addition is commutative. So the count of $1$'s below the main diagonal equals the counts of $1$'s above the main diagonal and the two counts combined form an even number. If we remember to add the sole $1$ for the entry $a_{11}$ then there are an odd number of entries in $A(n)$. In particular $|A(n)|$ is always odd.

$\underline{\text{lemma 2}}:$ As mentioned earlier every matrix $A(n)$ has $2n-1$ skew diagonals. Let $S_n$ be the $n$-th skew diagonal of $A(n)$. A skew analogue of Bertrand's Postulate shows that at least one of the skews between $S_n$ and $S_{2n-2}$ has all of its entries equal to $1$. Consequently for $n>2$ we have that there is always a skew diagonal with entries equal to $1$ below the main skew diagonal. In particular $\{A(n)\}_{n=1}^\infty$ is a monotonically increasing sequence of odd integers.

Lemma's 1 and 2 control the growth of $A(n)$ as $n \to \infty.$ By parity check alone as $A(n)$ grows to $A(n+1)$ the count of new $1$'s must be an nonzero even number. Because of this we have that $|A_n|=|A_{n-1}|+2j$ for some $j\in\mathbb{N}$, $j\neq0$. So we have the following from direct substitution

\begin{align} {|A_{n}|+|A_{n-2}| \above 1.5pt|A_{n-1}|}&={\left(|A_{n-1}|+2j\right)+\left(|A_{n-1}|-2k\right)\above 1.5pt |A_{n-1}|}\\ &=2\cdot{|A_{n-1}|+j-k\above 1.5pt |A_{n-1}|}\\ &=2\cdot\left(1+{j-k\above 1.5pt |A_{n-1}|}\right)\\ \end{align}

Taking limits we have \begin{align} \lim_{n\to \infty}2\cdot\left(1+{j-k\above 1.5pt |A_{n-1}|}\right)&=2+\lim_{n\to \infty}\left({j-k\above 1.5pt |A_{n-1}|}\right)\\ &=2+0\\ &=2 \end{align}

This completes the proof.

$\endgroup$
  • $\begingroup$ You have posted a question and solution – so what are you asking for? $\endgroup$ – Martin R Feb 21 '18 at 14:15
  • $\begingroup$ ^ I wrote it in the question box at the top of the post: I ask if the limit is true and how can we show it. $\endgroup$ – Antonio Hernandez Maquivar Feb 21 '18 at 14:16
  • $\begingroup$ Are you asking for a [proof-verification] ? $\endgroup$ – Martin R Feb 21 '18 at 14:17
  • $\begingroup$ Sort of. I am not sure my solution is correct but I wanted to show the work and effort I put in to try and solve it. $\endgroup$ – Antonio Hernandez Maquivar Feb 21 '18 at 14:19
  • $\begingroup$ Do you have any data for $|A_{n-1}|/|A_{n}|$? How it behaves? $\endgroup$ – Seewoo Lee Feb 21 '18 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.