Saturday 18 November 2023

Simon Marais 23B4 revisited + comments on official solution

(SM2023, B4) Let $n$ be a non-square number. 

(a) Find all pairs of natural numbers $(a,b)$ so that $r^a+\sqrt{n}, r^b+\sqrt{n}$ are both rational for some positive real $r$.
(b) Find all pairs of natural numbers $(a,b)$ so that $r^a+\sqrt{n}, r^b+\sqrt{n}$ are both rational for some real $r$. This is an open question currently.

When I first drafted my quick comment I simply omitted this question because a Q4 is a Q4 and has to be respected, so I only left one or two sentences there. Later on I found this one of interest so I dived in and wrote a simple answer. But then some gap in the solution had been lingering in my mind, and unsurprisingly I missed out something important so the answer is not fully correct. But I feel like I am close to the answer since the math behind is nothing overly complicated.

Below is my later attempt. There is a gap still, not recommended for readers.


Obviously, every $a=b$ pair is a solution because you can easily make up $r = (n-\sqrt{n})^{1/a}$. Next, if $(a,b)$ is a solution then so as its multiples $(ka,kb)$ because you can take $r' = r^{1/k}$. 

As a result we can now assume that $a,b$ are coprime. As $r^a, r^b \in \mathbb{Q}[\sqrt{n}]$, we know that $r\in \mathbb{Q}[\sqrt{n}]$ as well. I think this is well known -- but in case that is not, think about Euclidean algorithm (recall that a field is Euclidean...or even simpler the algorithm where you find gcd) that you can divide each other until you reach $r^1 = r$. 

Now write $r= p-q\sqrt{n}$ for some positive rational $p,q$ (the proofs are similar for different sign combination. Like you can write $r = p+q\sqrt{n}$ can the argument below proceeds the same). If you still remember your linear algebra lesson you can solve the recurrence by writing $p_k-q_k \sqrt{n} = (p-q\sqrt{n})^k$ for rational $(p_k), (q_k)$. For $v_k = (p_k,q_k)^t$, we have $v_k = A^{k}v_0$ where $A = \begin{bmatrix}p & nq\\ q & p\end{bmatrix}$.

The general formula for $p_k,q_k$ can be easily obtained by either method of eigenvectors or if you know how expand binomial powers. Anyway we have: 
$p_k = \frac{1}{2}((p+q\sqrt{n})^k+(p-q\sqrt{n})^k)$
$q_k = \frac{1}{2\sqrt{n}}((p+q\sqrt{n})^k-(p-q\sqrt{n})^k)$.
Notice that the formula is the same for $(p+q\sqrt{n})^k$. For negative $p,q$ the sign just alternates. 

Clearly $q_k$ is an alternating almost exponential series. More precisely we expect $q_{2k}-1 \approx q(p+q\sqrt{n})^{2k-2}$ and $q_{2k}\approx 2pq(p+q\sqrt{n})^{2k-2}$. The two subsequences are surely strictly monotonic and would not give us any non-trivial answer. The difficult task is however to find $k,k'$ so that $q_{2k} = q_{2k'-1}$.

A few approaches are there: first you may want to show that $q_n$ may not even be an integer if $p,q$ are (non-integral) fractions past a certain $k$. Secondly you may consider something even stronger that $q_k$ can't be 1 for largr $k$ because exponential sequences are either diverging or goes to zero, but the problem is you can always make very marginal case where $(p+q\sqrt{n})$ is very close to 1 (e.g. using continued fractions) so that the 'rate of divergence' is not properly bounded.

The problem for us is (1) we can't calculate terms manually for anything past $k=4$ -- even that is nasty enough as you can see below, and (2) what is the meaning of (b) being unsolved? Most arguments, if we assume that $r\in \mathbb{Q}[\sqrt{n}]$, does not really care about its positivity. In fact, we care if $(p-q\sqrt{n})$ being negative or not more so $(1-2\sqrt{2})^k$ is easier to handle than $(1+2\sqrt{2})^k$!

My approach is basically the observation that the last $k$ where $q_k$ can easily be made as an integer when $p,q\notin \mathbb{Z}$ is $q_4$ with where $(\frac{1}{2} + \frac{3}{2}\sqrt{3}) = \frac{223}{4} + 21\sqrt{3}$. One suspects that for larger $k$ the expansion looks like $q_k = kp^{k-1}q + cnp^{k-3}q^3 + c'n^2q^5(...)$, where the $n^2$ is causing problems when we want to solve integrality or doing mod checks. But at the end the approach does not distinguish between (a) and (b). Now I am really confused...and I see nothing wrong in the Euclidean argument too. 

Still, let us try to check the lower $q_k$'s:

$q_1 = q$
$q_2 = 2pq$
$q_3 = 3p^2q + nq^3$
$q_4 = 4pq(p^2+nq^2)$

As claimed, $q_1\neq q_3$ and $q_2\neq q_4$ so we only need to solve the 12,14,23,34 pairs.

$q_1=q_2=1$: this is easy with $p = \frac{1}{2}$ and $q=1$. Possibly a solution that students would have noticed without going through all these hassle.

$q_2=q_3=1$: Substitution gives the quintic equation $8p^4 - 4p^3 + n = 0$ with discriminant $256n^2(512n-27)$. By checking $(512n-27)$ mod 8 we know this is a non-square so that gives no rational solution.

$q_1=q_4=1$: Substitution gives the equation $4p(p^2+n)-1 = 4p^3 + 4np-1 = 0$. Surely one real root but the discriminant of a cubic equation doesn't tell much about rationality. Instead we convert $p$ into a fraction $p = \frac{s}{t}$ so $4p(p^2+n)$ becomes $\frac{4s(s^2+nt^2)}{t^3}$ for some $(s,t)=1$ but then we require $t^2\mid s^2$ which is absurd.

$q_3=q_4=1$: this is of course the hardest...but the technique never changes. From $q_3=1$ we obtain $q = (4p-1)/8p^3$. Substitution into $q_4=1$ gives a horrible degree 9 equation 
$3p^2((4p-1)/(8p^3)) + n((4p-1)/(8p^3))^3$
$ = (n(4p-1)^3 - 3\times 64p^2 + 3\times 256p^3)/512p^9 = 1$. 
Looks horrible but all we need is to take mod $p^2$ which eliminates the last two terms. Since $(p,4p-1)=1$ that forces $n$ to be non-square-free, hence the contradiction. So $(a,b) = (k,k)$ or $(k,2k)$ are all the possible pairs.

Other than discriminant checking, the main trick is to force a term to be multiple of $p^2$ (or anything else) if you want the sum to be a multiple of $n^2$ and so does the rest of the terms, then we can apply the square-free assumption. I believe this can be applied for higher $q_k$'s because we can check higher powers of $p$ against the $n^2$ factor. But clearly (b) being open does not support that.

So, basically the sure answers are in forms of $(a,b) = (k,k)$ or $(k,2k)$. But are there more? I don't know.

The more I think about this question the more I like it with so many different scattered technique that were used. This is the type of question we would like to see more. I would not hide the fact that my first attempt is a miserable fail as I overlooked a large part of it. I wrote that we look at $A^2$ again we know from there that the denominator would sure to stack up every 2 steps, but what about consecutive terms $q_k$ and $q_{k+1}$? I stared at what I wrote before I finally realized what should be corrected...but nope I am probably not getting 7 this time.

Just food for thought...what if we are now in $\mathbb{Q}[\sqrt{-n}]$, or that $(a,b)$ are simply integers instead? 

--------------------(NEW 08/12/2023)---------------------------

The solution is out and below is my answer-checking...

A1. No surprise, but their solution 3 is neat. If you skipped that while reading the solution you should go and have a check.

A2. The idea is right but I got the lower bound wrong for not considering $S$ to be set of all possible convex functions, but that is still easy.

A3. Completely wrong...hmmm I totally missed the 'unequal size' condition. Instead I took the sets $A_i$ in the way that $A_i$'s are not pairwise subsets and supsets. The correct version of A3 is much easier. Still I appreciate they put all the details unlike me (especially A2 and A3).

A4. As expected but their approach of finding the 'crtical point' is more elegant than calculus bashing.

B1-B3 are all as expected. But they spent more words on B2 that I would have thought. At this point I think all Simon Marais contestants should learn generating functions before they come -- such question appears almost every year!

B4. Here is the big thing -- I say that I can't see how should I tweak the solution to accustom the condition that distinguishes (a) and (b). How about scrapping the whole approach? It is now clear that my approach is more for (b) the open problem. (a) is much easier. I also missed that fact that for $(a,b) = (1,2)$ we actually got a negative solution so that does not count in (a) but in (b)...

No surprise in C1-C3 again, though C3 should deserve only a one-line solution if any.

No comments:

Post a Comment