Thursday, 12 November 2026

Maths with AI

Looking at the breakthroughs achieved by AI models in mathematics in recent times, I gave it a try a few weeks ago to see if as a non-mathematician, I could use GPT to do some hard mathematics.
Using a free account of GPT, I posted a hard question in the chat and asked GPT to solve it. I reached a solution a few hours later which I have shared below, along with my experience itself of working with AI, which was perhaps more enlightening for me than the actual mathematical results.

Experience of doing Maths with AI

- Given a hard question that GPT cannot quickly solve, it thinks for some time and then posts some partial success or ideas, followed by suggested next step that it thinks it should follow. Once I give it a reply, again it comes back with next partial success or ideas, followed by suggested next step. The model keeps doing this in a loop, and after each iteration it checks in with me to make sure I'm ok with the direction it is heading in.

- In the beginning, I understood most of what it said, and was able to give meaningful opinions on next step. As it went deeper and deeper into advanced mathematics, I was only able to understand broadly what it said, and soon there were sections where the maths involved concepts I had not even heard of. In such cases, I pretended to nod along and just kept telling it to proceed with its suggested next step.

- As an approach, when GPT is stuck, it first tries to understand the shape of underlying reality, with the belief that the knowledge gained will help find the next steps. More importantly, it explains to the reader as well why it thinks a particular exploration will result in useful insights for the next step. If the gained insights are not as per expectations, it explains how it is interpreting this new insight and how it is re-calibrating its approach accordingly. This was a surprise for me. I had assumed that working with AI would result in an opaque discovery of final results, without any new learnings that explain how to get there, or that can be used in other hard problems. This will likely be true if you only read the final result, its theoroems, and proofs, but not if you also read AI's intermediate explorations and insights.
Perhaps AI companies that publish mathematical breakthroughs should also share these intermediate reasonings to showcase how AI can collaborate with mathematical community instead of it only being a result generator. Below I have shared only the final theorems and proofs, but let me know if you are interested in the entire chat.

Problem given to GPT

I first gave GPT a solved problem to see how it reacts.
The problem was to find necessary and sufficient conditions so that an infinitely nested radical \( P=\sqrt{a_1+\sqrt{a_2+\sqrt{a_3+\cdots}}} \) converges to a real number.
GPT correctly provided the solution along with the original author's name.


Then, I gave the hard problem of generalising the result.
I asked GPT to look at the nested radical \( \sqrt{A_1 + B_1\sqrt{A_2 + B_2\sqrt{A_3 + B_3\sqrt{\cdots}}}} \)
where \(B_n\) can be mixture of positive and negative numbers, and asked it to find necessary and sufficient condition that this radical converges to a real number.
As far as I know, this is not a solved problem, but I could be completely wrong because I am not connected to the world of mathematical research.

AI's approach

GPT decided that we should first focus on the scenario where all \(Bn\) are negative and try and solve it. Once done, we can decide to come back for exploring mixed positive and negative signs. So, we focused on radicals with all negative signs, and GPT successfully solved this in a few hours.
I asked it to give a summary for this result (omitting all the dead ends and any intermediate insights that were not ultimately needed by the proof), and below is the summary generated by GPT. Perhaps next week, I'll ask GPT to continue its exploration into radicals with mixed signs.

See you then!


Summary by GPT: Convergence of Infinitely Nested Radicals

PART I. Nested radicals with all positive signs

1. Herschfeld's theorem
Consider \[ P=\sqrt{a_1+\sqrt{a_2+\sqrt{a_3+\cdots}}}, \qquad a_n\geq0. \] Let \(P_{n,N}\) denote the finite radical beginning at position \(n\) and ending at position \(N\): \[ P_{n,N}=\sqrt{a_n+P_{n+1,N}}, \qquad P_{N+1,N}=0. \] The question is when \(P_{1,N}\) converges to a finite limit as \(N\to\infty\).

Theorem 1 — Herschfeld's convergence theorem
The infinite positive nested radical converges to a finite real number if and only if \[\boxed{ \sup_{n\geq1}a_n^{1/2^n}<\infty. } \tag{1} \] Thus the terms \(a_n\) must grow no faster than a constant raised to the power \(2^n\).

Proof
Necessity.
From the finite radical recursion, \[P_{n+1,N}\leq P_{n,N}^2\] Repeated application gives \[P_{n,N}\leq P_{1,N}^{2^{n-1}}\] Since \(a_n\leq P_{n,N}^2\), \[a_n^{1/2^n}\leq P_{1,N}\] If the infinite radical converges to a finite value \(P\), letting \(N\to\infty\) gives \[a_n^{1/2^n}\leq P\] Hence the sequence in (1) is bounded.
Sufficiency.
Suppose there is an \(M\geq1\) such that \[a_n\leq M^{2^n}\] for every \(n\). Normalize the finite radicals by \[Y_{n,N}=\frac{P_{n,N}}{M^{2^{n-1}}}\] Then \[Y_{n,N}^2 = \frac{a_n}{M^{2^n}}+Y_{n+1,N} \leq1+Y_{n+1,N} \] Let \[\varphi=\frac{1+\sqrt5}{2},\] so that \(\varphi^2=1+\varphi\). Starting from the terminal value \(Y_{N+1,N}=0\), backward induction gives \[Y_{n,N}\leq\varphi\] In particular, \[P_{1,N}\leq M\varphi\] Finally, \(P_{1,N}\) is nondecreasing as \(N\) increases, because all terms are nonnegative and every radical transformation is increasing. It is also bounded above.
Therefore it converges.

\(\square\)

Significance
The critical growth scale is \(2^n\). For example, \[a_n=C^{2^n}\] produces a convergent positive nested radical for every fixed \(C>0\).
Conversely, sufficiently rapid growth beyond this scale forces divergence.

2. Positive multipliers
We also considered the generalized positive form \[P=\sqrt{a_1+b_1\sqrt{a_2+b_2\sqrt{a_3+\cdots}}}, \qquad a_n,b_n>0\] This can be reduced to Herschfeld's theorem by rescaling. Define \[c_1=1,\qquad c_{n+1}=\frac{c_n^2}{b_n},\] and write \[P_n=c_nY_n\] Then \[Y_n=\sqrt{\frac{a_n}{c_n^2}+Y_{n+1}}\] Consequently:

Corollary 1 — Positive radicals with multipliers
The generalized positive nested radical converges if and only if \[ \boxed{ \sup_{n\geq1} \left(\frac{a_n}{c_n^2}\right)^{1/2^n} \lt \infty, \qquad c_{n+1}=\frac{c_n^2}{b_n},\quad c_1=1 } \tag{2} \] Thus positive multipliers do not require a fundamentally different convergence theory; they modify the effective coefficients.

PART II. Normalization of all-negative nested radicals

3. The general all-negative form
Consider \[R_1=\sqrt{A_1 - B_1\sqrt{A_2 - B_2\sqrt{A_3 - B_3\sqrt{\cdots}}}},\] where \(A_n, B_n>0\). Write the tail beginning at position \(n\) as \[R_n=\sqrt{A_n-B_nR_{n+1}}\] Normalize by putting \[R_n=\sqrt{A_n}\,Z_n\] Substitution gives \[Z_n = \sqrt{1 - \frac{B_n\sqrt{A_{n+1}}}{A_n}Z_{n+1} }\] Define the normalized coefficient \[ \boxed{\gamma_n=\frac{B_n\sqrt{A_{n+1}}}{A_n}} \tag{3} \] Our all-negative results apply to the admissible normalized regime \[0 \lt \gamma_n \leq 1.\] The normalized problem is therefore \[ \boxed{R=\sqrt{1 - \gamma_1\sqrt{1 - \gamma_2\sqrt{1 - \gamma_3\sqrt{\cdots}}}}} \tag{4} \] And it suffices to study the convergence of this normalized radical. For the rest of the summary, \(R\) denotes this normalized radical.
Define the individual radical transformation \[ \boxed{f_\gamma(x)=\sqrt{1-\gamma x}, \qquad 0\leq x\leq1} \tag{5} \] Unlike the positive case, every \(f_\gamma\) is decreasing.
This reversal of monotonicity is responsible for the different convergence behaviour.

4. Exact finite-interval formulation
For a finite truncation at depth \(N\), start with \[I_{N+1,N}=[0,1]\] Propagate backwards: \[I_{n,N}=f_{\gamma_n}(I_{n+1,N})\] Write \[I_{n,N}=[p_{n,N},u_{n,N}]\] Because \(f_{\gamma_n}\) is decreasing, \[ \boxed{\begin{aligned} p_{n,N}=\sqrt{1-\gamma_nu_{n+1,N}},\\ u_{n,N}=\sqrt{1-\gamma_np_{n+1,N}}. \end{aligned} } \tag{6} \]

Theorem 2 — Exact interval-width criterion
The infinite normalized all-negative radical converges if and only if \[ \boxed{ \lim_{N\to\infty}(u_{1,N}-p_{1,N})=0. } \tag{7} \]

Proof

The intervals \(I_{1,N}\) are nested as \(N\) increases. Their endpoints are the two possible values obtained by terminating the finite radical with terminal tails zero and one.
Thus the even- and odd-depth truncations lie at the two endpoints of these intervals, with their order alternating.
If the widths tend to zero, both truncation subsequences approach the same limit.

Conversely, if the truncations converge, their difference tends to zero, and hence the interval widths tend to zero.

\(\square\)

There is also an exact product identity.
Let \[W_{n,N}=u_{n,N}-p_{n,N}\] Rationalizing the difference of the two square roots gives \[W_{n,N} = \frac{\gamma_n}{p_{n,N}+u_{n,N}}W_{n+1,N}\] Since the terminal width is one, \[ \boxed{W_{1,N} = \prod_{n=1}^{N} \frac{\gamma_n}{p_{n,N}+u_{n,N}}} \tag{8} \] This is an exact necessary-and-sufficient condition, though it still requires recursively calculating the endpoints.

PART III. The two-coefficient transformation and its contraction
5. Group coefficients into pairs
The natural unit of analysis for negative radicals is a pair of consecutive coefficients.
Write \[a_k=\gamma_{2k-1}, \qquad b_k=\gamma_{2k}\] Define the increasing two-level transformation \[ \boxed{F_k(x)=f_{a_k}(f_{b_k}(x)) = \sqrt{1-a_k\sqrt{1-b_kx}}} \] The key property is that every such pair strictly contracts interval uncertainty in a suitable metric.
Introduce the log-odds coordinate \[ \boxed{\ell(x)=\log\frac{x}{1-x}, \qquad d(x,y)=|\ell(x)-\ell(y)|} \tag{9} \]

6. Uniform contraction of every coefficient pair

Lemma 1 — Pair contraction
For every \(a,b\in(0,1]\), and every interval \(I\subset(0,1)\), \[ \boxed{\operatorname{diam}_{d}\big(f_a\circ f_b(I)\big) \leq q\,\operatorname{diam}_{d}(I),} \tag{10} \] where \[ \boxed{q=\frac34+\frac{\sqrt3}{8} \lt 1} \] The numerical value is approximately \(0.966506\).

Proof
First consider a single transformation \(f_\gamma\).
Take \(0 \lt x \lt y \lt 1\), and put \[s=f_\gamma(x),\qquad r=f_\gamma(y)\] Then \(s>r\).
Define \[P=\log\frac yx,\qquad Q=\log\frac{1-x}{1-y},\] and \[T=\log\frac sr+\log\frac{1+s}{1+r}\] Using \[1-f_\gamma(x)=\frac{\gamma x}{1+f_\gamma(x)},\] we find that the input and output log-odds widths are respectively \[P+Q,\qquad P+T\] Also, \[Q\geq2\log\frac sr\] and \[T\leq2\log\frac sr\] Hence \(T\leq Q\), proving that a single transformation never increases log-odds width.

Now suppose the input interval lies in \([1/2,1)\). Then \(P\leq Q\).
If \(\gamma\geq1/2\), then \(s\leq\sqrt3/2\). Using \[\log\frac{1+s}{1+r} \leq(s-r)\leq s\log\frac sr,\] we get \[T\leq \frac{1+\sqrt3/2}{2}Q\] If \(\gamma \lt 1/2\), then \(s,r>1/\sqrt2\), which gives \[T\leq\frac1{\sqrt2}Q\] Both estimates imply \[T\leq q_0 Q, \qquad q_0=\frac12+\frac{\sqrt3}{4}\] Therefore, \[\frac{P+T}{P+Q} \leq \frac{1+q_0}{2} = \frac34+\frac{\sqrt3}{8}=q\] A single transformation thus contracts log-odds width by \(q\) whenever its input interval lies above \(1/2\).

Finally consider \(f_a\circ f_b\).
- If the input interval lies below \(1/2\), the inner transformation maps it above \(1/2\), so the outer transformation contracts.
- If the input lies above \(1/2\), the inner transformation contracts, and the outer one is non-expanding.
- If the interval crosses \(1/2\), split it there and apply the preceding two arguments to the two pieces.
The pair therefore contracts by \(q \lt 1\) in every case.

\(\square\)

This result is fundamental: every two consecutive negative-radical levels reduce log-odds uncertainty by a fixed proportion.
The remaining challenge is to ensure that the uncertainty is initially bounded in this metric.

PART IV. Periodic all-negative coefficients

The contraction theorem allows us to classify every periodic coefficient sequence.


7. Period 1 — Constant coefficient
Suppose \[\gamma_n=a \qquad\text{for every }n\]
Theorem 3 — Period 1
\[ \boxed{ \begin{cases} 0 \lt a \lt 1 &: \text{the radical converges},\\ a=1 &: \text{the radical diverges}. \end{cases} } \] When \(0 \lt a \lt 1\), its value is \[ \boxed{R=\frac{\sqrt{a^2+4}-a}{2}} \tag{11} \]

Proof
For \(a \lt 1\), the pair transformation maps \([0,1]\) strictly into \((0,1)\). Repeated application contracts log-odds width by Lemma 1, so the radical converges.
Since the coefficients are constant, the limiting value satisfies \[R=\sqrt{1-aR}\] Solving the quadratic equation gives (11). If \(a=1\), the finite truncations alternate between one and zero, so the radical diverges.

\(\square\)

For example, at \(a=1/2\), \[R=\frac{\sqrt{17}-1}{4}\approx0.780776\]

8. Period 2 — Two alternating coefficients
Suppose \[(\gamma_n)=(a,b,a,b,a,b,\ldots)\] Theorem 4 — Period 2
\[ \boxed{\text{The radical converges} \iff a \lt 1\text{ and }b \lt 1} \tag{12} \] When it converges, the two alternating tail values \(x,y\) satisfy \[ \boxed{x=\sqrt{1-ay}, \qquad y=\sqrt{1-bx}} \tag{13} \]

Proof

If both coefficients are below one, the pair transformation maps \([0,1]\) strictly into \((0,1)\). Repeated application contracts log-odds width by Lemma 1.

Suppose instead that \(a=1\). The odd-position coefficients are all one. By the boundary theorem in Section 8, convergence would require \[\sum_{k=1}^{\infty}2^{-k}\log\frac1b=+\infty\] This series is finite for every fixed \(b>0\). Hence the radical diverges.
The case \(b=1\) is symmetric.

\(\square\)

An important consequence is that the two alternating coefficients need not be equal.


9. Period 3 — Three alternating coefficients
Suppose \[(\gamma_n)=(a,b,c,a,b,c,\ldots)\] Theorem 5 — Period 3
\[ \boxed{ \text{The radical converges} \iff \min(a,b,c) \lt 1} \tag{14} \] When it converges, the three repeating tail values satisfy \[ \boxed{ \begin{aligned} x&=\sqrt{1-ay},\\ y&=\sqrt{1-bz},\\ z&=\sqrt{1-cx}. \end{aligned} } \]
Proof
Consider two complete periods, giving the six-level transformation \[F=f_a\circ f_b\circ f_c\circ f_a\circ f_b\circ f_c\] Since the period length is odd, every coefficient occurs once at an odd position and once at an even position in this two-period block.
If at least one coefficient is below one, the six-level transformation maps \([0,1]\) strictly into \((0,1)\). It consists of three two-level transformations, each contracting by Lemma 1.
Repeated application therefore forces the interval width to zero.
If all three coefficients equal one, the finite truncations alternate between zero and one, so the radical diverges.

\(\square\)

10. Every odd period

The period-3 result generalizes directly.


Theorem 6 — Arbitrary odd periods
Suppose the coefficients have an odd period \(p\). Then \[ \boxed{ \text{The radical converges} \iff \exists j\in\{1,\ldots,p\}:\gamma_j \lt 1} \tag{15} \] Thus one subcritical coefficient anywhere in an odd period is sufficient.
Proof
Consider two complete periods, giving a block of length \(2p\).
Because \(p\) is odd, the second occurrence of every coefficient is shifted to the opposite positional parity.
Therefore, if at least one coefficient in the period is below one, the two-period block contains a subcritical coefficient in both parity classes.
An even-length composition with a subcritical coefficient in each parity class maps \([0,1]\) strictly into \((0,1)\).
It consists of \(p\) two-level transformations, so its log-odds contraction factor is at most \(q^p \lt 1\).
Repeated two-period blocks therefore force the interval width to zero.
If all coefficients are one, the radical diverges.

\(\square\)

11. Every even period

For even periods, the answer is different.


Theorem 7 — Arbitrary even periods
Suppose the coefficients have an even period \(p\).
Then \[ \boxed{ \begin{aligned} \text{R converges} \iff{} &\text{at least one odd-position coefficient}\\ &\text{in the period is below one, and}\\ &\text{at least one even-position coefficient}\\ &\text{in the period is below one.} \end{aligned} } \tag{16} \]
Proof
Consider one complete period, which has even length.
Its composition maps \([0,1]\) strictly into \((0,1)\) precisely when there is at least one coefficient below one at each positional parity.
If both are present, the period consists of \(p/2\) two-level transformations. Its log-odds contraction factor is at most \[ q^{p/2} \lt 1 \] Repeated application therefore gives convergence.
If one parity consists entirely of ones, the boundary theorem in Section 8 requires a geometrically weighted logarithmic series over the other parity to diverge.
For a periodic sequence with strictly positive coefficients, that series is finite. Hence the radical diverges.

\(\square\)

Corollary — Period 4
For the period-four pattern \[(a,b,c,d,a,b,c,d,\ldots),\] convergence occurs precisely when \[ \boxed{\min(a,c) \lt 1 \quad\text{and}\quad \min(b,d) \lt 1} \tag{17} \] For example, \[(a,1,1,b,a,1,1,b,\ldots)\] converges whenever \(a,b \lt 1\).

Consolidated periodic classification
\[ \begin{array} \text{Period} & \text{Necessary-and-sufficient condition} \\ \text{1} & \text{Constant coefficient below one} \\ \text{2} & \text{Both coefficients below one} \\ \text{3} & \text{At least one coefficient below one} \\ \text{Any odd period} & \text{At least one coefficient below one} \\ \text{Any even period} & \text{At least one coefficient below one} \\ & \text{on each positional parity} \\ \end{array} \] The fundamental distinction is that odd periods interchange the two positional parities after one period, whereas even periods preserve them.

PART V. Exact results for non-periodic boundary sequences

The next two results are particularly useful because they give simple series criteria without requiring periodicity.


12. All odd-position coefficients equal one
Suppose \[ \boxed{\gamma_{2k-1}=1,\qquad \gamma_{2k}=b_k} \tag{18} \] Theorem 8 — Odd positions at the boundary
The infinite radical converges if and only if \[ \boxed{ \sum_{k=1}^{\infty} 2^{-k}\log\frac1{b_k}=+\infty } \tag{19} \] When it converges, its value is zero.

Proof
The two-level transformation at pair \(k\) is \[F_k(x)=\sqrt{1-\sqrt{1-b_kx}}.\] Since \(F_k(0)=0\), the lower endpoint of every finite root interval is zero.
The radical therefore converges precisely when the upper endpoint tends to zero. Equivalently, the corresponding even-position tail must tend to one.
Write that even-position tail as \(Y_k\). It satisfies \[Y_k=\sqrt{1-b_k\sqrt{1-Y_{k+1}}}\] Define \[t_k=-\log(1-Y_k)\] Using \[1-\sqrt{1-x} = \frac{x}{1+\sqrt{1-x}},\] we obtain \[ \boxed{t_k= \frac12t_{k+1} +\log\frac1{b_k} +\log(1+Y_k)} \tag{20} \] The final term lies between zero and \(\log2\).
Iterating the recurrence over a finite truncation shows that \(t_1\) differs from the geometrically weighted sum \[\sum_{k=1}^{N}2^{-(k-1)}\log\frac1{b_k}\] by a bounded quantity independent of \(N\).
Thus \(t_1\to+\infty\) precisely when the series in (19) diverges.
Since \(t_1\to+\infty\) is equivalent to \(Y_1\to1\), this proves the theorem.

\(\square\)

13. All even-position coefficients equal one
The reverse arrangement is \[ \boxed{\gamma_{2k-1}=a_k,\qquad \gamma_{2k}=1} \tag{21} \] Theorem 9 — Even positions at the boundary
The infinite radical converges if and only if \[ \boxed{\sum_{k=1}^{\infty} 2^{-k}\log\frac1{a_k}=+\infty} \tag{22} \] When it converges, its value is one.
Proof
In this case, the upper endpoint of every finite root interval is one.
Convergence requires the lower endpoint to tend to one.
The corresponding odd-position tail satisfies \[X_k=\sqrt{1-a_k\sqrt{1-X_{k+1}}}\] Defining \(t_k=-\log(1-X_k)\) gives exactly the recurrence (20), with \(a_k\) replacing \(b_k\).
The same argument proves condition (22).

\(\square\)

These boundary theorems also cover sequences with an arbitrary finite prefix, since a finite prefix of strictly monotone transformations does not change whether an interval has collapsed to a single point.


PART VI. The uniform two-coefficient approximation
The periodic results explain the importance of pairing consecutive coefficients. To handle arbitrary sequences, we need a stronger result: a description of how an arbitrary pair changes an interval of possible tail values.
This is the technical foundation of the general theorem.

14. The pair transformation in log-odds coordinates
For a pair \(a,b\), define \[A=\log\frac1{1-a}, \qquad B=\log\frac1{1-b}, \qquad G=\log\frac1b\] Also define \[L=G-A,\qquad U=B,\] and \[p=-\log(1-\sqrt{1-a})\] When \(a=1\), we have \(p=0\) and \(L=-\infty\). The two-level transformation is \[F(x)=\sqrt{1-a\sqrt{1-bx}}\] In log-odds coordinates, it becomes \[ \boxed{h(z)=\ell(F(\sigma(z)))} \tag{23} \] Define the clipping function \[\operatorname{clip}(z;L,U) = \min\{\max(z,L),U\},\] with the natural limiting conventions for infinite endpoints.

15. Uniform pair approximation theorem


Lemma 2 — Clipped-affine approximation
There is an absolute constant \[C_0=4\log2\] such that the exact pair transformation can be approximated uniformly by \[ \boxed{\tau(z)=p-\frac G2+\frac12\operatorname{clip}(z;L,U)} \tag{24} \] If \(L>U\), the window is empty and \(\tau\) is instead the constant \(h(-\infty)\).
For every \(a,b\in(0,1]\), \[ \boxed{\sup_{z\in\mathbb R}|h(z)-\tau(z)| \leq C_0} \tag{25} \] The crucial feature is that the constant does not depend on the coefficients.
Proof
Put \[x=\sigma(z),\qquad y=\sqrt{1-bx},\qquad v=\sqrt{1-ay}\] Direct algebra gives \[h(z)=K(z)-\log a+\frac12J_B(z), \tag{26} \] where \[K(z)=\log(v(1+v))\] and \[J_B(z) = \log(1+e^z)-\log(1+e^{z-B})\] First, the elementary inequality \[0\leq\log(1+e^t)-\max(t,0)\leq\log2\] gives \[ \boxed{|J_B(z)-\operatorname{clip}(z;0,B)| \leq2\log2} \tag{27} \] Now suppose \(a \lt 1\), and write \[\delta=1-a=e^{-A}, \qquad q=a(1-y)\] Since \(v^2=\delta+q\), \[K(z)-K(-\infty) = \frac12\log\left(1+\frac q\delta\right) + \log\frac{1+v}{1+\sqrt\delta} \tag{28} \] The second term lies between zero and \(\log2\).
Using \[1-y=\frac{b\sigma(z)}{1+y},\] we obtain \[ \boxed{\frac q\delta = (1-e^{-A}) \frac{e^{z-L}}{(1+e^z)(1+y)}} \tag{29} \] Define \[C_L(z)= \begin{cases} \min\{\max(z-L,0),-L\},&L \lt 0,\\ 0,&L\geq0. \end{cases} \] A direct division into the ranges \(z\leq L\), \(L\leq z\leq0\), and \(z\geq0\) gives \[ \boxed{\left| \log\left(1+\frac q\delta\right)-C_L(z) \right| \leq\log8} \tag{30} \]

For example, when \(L \lt 0\) and \(a\geq1/2\), equation (29) shows that the ratio \(q/\delta\) is between \(e^{z-L}/8\) and \(e^{z-L}\) in the middle range, and between \(e^{-L}/8\) and \(e^{-L}\) in the upper range. When \(a \lt 1/2\), we have \(A \lt \log2\), so the required error is directly bounded.


Combining (28) and (30), \[\left| K(z)-K(-\infty)-\frac12C_L(z) \right| \leq\frac52\log2\] For \(L\leq0\), the identity \[C_L(z)+\operatorname{clip}(z;0,B) = \operatorname{clip}(z;L,B)-L\] gives the approximation (24), using \[K(-\infty)-\log a=p-\frac A2\] If \(0 \lt L\leq B\), the replacement changes the clipped expression by at most \(L\). But \[L \lt G,\qquad L\leq B,\] and \[\min(B,G)\leq\log2\] Thus the extra error is at most \(\frac12\log2\).
If \(L>B\), then the window is empty. In this case \(B \lt L \lt G\) and \(B \lt \log2\); equation (29) shows that the variation of \(h\) from \(h(-\infty)\) is at most \(2\log2\).
Finally, if \(a=1\), then \(L=-\infty\). Direct substitution into (26) gives the required approximation with error at most \(2.5\log2\).
All cases are therefore covered by \(C_0=4\log2\).

\(\square\)

Interpretation

Every pair behaves approximately like a clipped affine map:
- Below its active window, the map is approximately constant.
- Inside the window, it has slope \(1/2\).
- Above the window, it is approximately constant again.
The approximation error is uniformly bounded, even when either coefficient approaches zero or one.

This is what allows us to handle arbitrary, highly oscillatory coefficient sequences.

PART VII. Discounted interval intersections
16. Compose the clipped maps
For the coefficient pair at position \(k\), write \[ \boxed{ \begin{aligned} a_k&=\gamma_{2k-1},\\ b_k&=\gamma_{2k},\\ A_k&=\log\frac1{1-a_k},\\ B_k&=\log\frac1{1-b_k},\\ G_k&=\log\frac1{b_k},\\ L_k&=G_k-A_k,\\ U_k&=B_k. \end{aligned} } \] Define \[ \boxed{c_k=-\log(1-\sqrt{1-a_k})-\frac12G_k} \tag{31} \] The approximate pair map is \[\tau_k(z)=c_k+\frac12\operatorname{clip}(z;L_k,U_k)\] when \(L_k\leq U_k\). For an empty window, use the constant approximation from Lemma 2.
Every nonconstant \(\tau_k\) is \(1/2\)-Lipschitz.
Consequently, after composing any number of pairs, the pointwise error between the exact and approximate compositions is bounded by \[C_0+\frac{C_0}{2}+\frac{C_0}{4}+\cdots \leq2C_0 \] The corresponding interval diameters therefore differ by at most \[4C_0=16\log2\]
17. The discounted windows
Define the discounted cumulative centre \[S_0=0,\qquad S_k=\sum_{r=1}^{k}2^{1-r}c_r\] For each pair, define the interval \[\boxed{K_k=[X_k^-,X_k^+],}\] where \[ \boxed{ \begin{aligned} X_k^-&=S_k+2^{-k}L_k,\\ X_k^+&=S_k+2^{-k}U_k. \end{aligned} } \tag{32} \]

If \(L_k>U_k\), the interval is empty.


Lemma 3 — Interval-intersection identity
The range of the clipped composition \[\tau_1\circ\tau_2\circ\cdots\circ\tau_N\] is exactly \[ \boxed{\bigcap_{k=1}^{N}K_k.} \tag{33} \]
Explanation
When every map uses its linear branch, the final output is \[c_1+\frac12c_2+\cdots+2^{1-N}c_N+2^{-N}z\] The requirement that the input to pair \(k\) lie in its window becomes \[X_k^-\leq z_{\rm output}\leq X_k^+\] Every such restriction must hold simultaneously. Their intersection is therefore the entire surviving output interval.
The identity also holds at the window boundaries because clipping maps the exterior of a window to its endpoints.

\(\square\)

18. Tail intervals and the exact convergence criterion
For every \(k\), define \[ \boxed{\Delta_k = \left[\inf_{j\geq k}X_j^+-\sup_{j\geq k}X_j^-\right]_+} \tag{34} \] This is the length of the intersection of all discounted windows from \(k\) onward.
Let \(d_k\) be the limiting log-odds diameter of the tail beginning at pair \(k\).
Provided both positional parities contain infinitely many coefficients strictly below one, the limiting tail intervals are interior to \((0,1)\), so these diameters are finite.
The pair approximation and the interval-intersection identity give \[ \boxed{|d_k-2^{k-1}\Delta_k|\leq16\log2} \tag{35} \] The quantities \(\Delta_k\) are nondecreasing: removing an early window restriction cannot reduce the intersection.

We can now establish:


Theorem 10 — Exact interval-intersection criterion
If both odd- and even-position coefficient subsequences contain infinitely many terms strictly below one, then \[ \boxed{ R\text{ converges} \iff \limsup_{k\to\infty}X_k^- \geq \liminf_{k\to\infty}X_k^+} \tag{36} \]

Proof
By the exact interval criterion, convergence at the root is equivalent to collapse of the root tail interval.
Since the finite prefix consists of strictly monotone transformations, the root interval collapses if and only if every fixed tail interval collapses.
If the radical converges, \(d_k=0\) for every \(k\). Equation (35) then gives \[0\leq\Delta_k \leq\frac{16\log2}{2^{k-1}}\] Since \(\Delta_k\) is nondecreasing and tends to zero, every \(\Delta_k\) must be zero.
Conversely, suppose every \(\Delta_k=0\). Equation (35) implies \[d_k\leq16\log2\] for every \(k\).
By Lemma 1, each two-level transformation contracts log-odds width by \(q \lt 1\). Therefore, \[d_1\leq q^{k-1}d_k \leq16\log2\,q^{k-1}\] Letting \(k\to\infty\), we obtain \(d_1=0\). Thus the radical converges.
Finally, \[\lim_{k\to\infty}\Delta_k = \left[\liminf_{k\to\infty}X_k^+- \limsup_{k\to\infty}X_k^- \right]_+\] Hence all the \(\Delta_k\) vanish precisely when the inequality in (36) holds.

\(\square\)

This is the bridge between the finite-width problem and a coefficient-only convergence condition.

PART VIII. Reduction to the general necessary-and-sufficient condition

The interval criterion can be simplified considerably.


19. Two weighted logarithmic series
Recall \[a_k=\gamma_{2k-1},\qquad b_k=\gamma_{2k}\] Define \[ \boxed{S_o=\sum_{k=1}^{\infty}2^{-k}\log\frac1{a_k}, \qquad S_e= \sum_{k=1}^{\infty}2^{-k}\log\frac1{b_k}} \tag{37} \] These are the odd- and even-parity weighted logarithmic series.
Also define the two parity-wise deficit measures \[\boxed{\eta_o= \liminf_{k\to\infty} 2^{-k}\log\frac1{1-a_k},}\] \[ \boxed{\eta_e=\liminf_{k\to\infty} 2^{-k}\log\frac1{1-b_k}} \tag{38} \] All quantities are interpreted in the extended nonnegative real numbers. In particular, \[\log\frac1{1-a_k}=+\infty\] when \(a_k=1\).

20. The high-low summability argument
We first work under the assumption that both parity classes contain infinitely many coefficients below one.
Define \[p_k=-\log(1-\sqrt{1-a_k}),\] and \[P_k=\sum_{r=1}^{k}2^{1-r}p_r,\qquad Q_k=\sum_{r=1}^{k}2^{-r}G_r\] Let \[R_k=P_k-Q_k\] Because \[p_k=\log\frac1{a_k}+\log(1+\sqrt{1-a_k}),\] the second term is bounded between zero and \(\log2\). Therefore, \[ \boxed{ \begin{aligned} P_k\text{ is bounded} &\iff S_o \lt \infty,\\ Q_k\text{ is bounded} &\iff S_e \lt \infty. \end{aligned} } \tag{39} \] Substituting the definitions into the discounted window endpoints gives \[ \boxed{ \begin{aligned} X_k^-&=R_k+2^{-k}G_k-2^{-k}A_k,\\ X_k^+&=R_k+2^{-k}B_k. \end{aligned} } \tag{40} \] Suppose the radical diverges.
By Theorem 10, the limiting intersection of the windows has positive length. Thus there are finite \(u \lt v\) such that, for every sufficiently large \(k\), \[X_k^-\leq u,\qquad X_k^+\geq v\] Put \[\theta=\frac{u+v}{2},\qquad \varepsilon=\frac{v-u}{2}>0\] Divide the indices into two classes.
High indices: \(R_k\geq\theta\).
The first inequality in (40) gives \[2^{-k}A_k\geq\varepsilon\] Hence \[A_k\geq\varepsilon2^k\] But \[p_k=-\log(1-e^{-A_k/2}),\] so, for sufficiently large \(k\), \[2^{1-k}p_k \leq 2^{2-k}e^{-\varepsilon2^{k-1}}\] The right-hand side is summable. Thus the increments of \(P_k\) over high indices are summable.
Low indices: \(R_k \lt \theta\).
The second inequality in (40) gives \[2^{-k}B_k>\varepsilon\] Therefore, \[2^{-k}G_k \leq 2^{1-k}e^{-\varepsilon2^k}\] Again, the right-hand side is summable. Thus the increments of \(Q_k\) over low indices are summable.
Now observe that \[ \boxed{R_k-R_{k-1} = (P_k-P_{k-1})-(Q_k-Q_{k-1})} \tag{41} \] On each consecutive run of high indices, \(R_k\) enters below \(\theta\) and leaves above it. Telescoping (41) shows that the total increment of \(Q_k\) on such a run cannot exceed the increment of \(P_k\).
Similarly, on each consecutive run of low indices, the total increment of \(P_k\) cannot exceed that of \(Q_k\).
The summability estimates above therefore force both \(P_k\) and \(Q_k\) to converge.
We have proved \[ \boxed{\text{Divergence of the radical} \Longrightarrow S_o \lt \infty\text{ and }S_e \lt \infty} \tag{42} \] This is the crucial reduction.

21. Finish the general criterion
Suppose now that both series converge.
Then \[R_k\longrightarrow R_\infty,\] and \[2^{-k}G_k\longrightarrow0\] Using (40), \[\limsup_{k\to\infty}X_k^- = R_\infty-\eta_o,\] and \[\liminf_{k\to\infty}X_k^+ = R_\infty+\eta_e\] The interval criterion (36) therefore becomes \[R_\infty-\eta_o \geq R_\infty+\eta_e\] Since \(\eta_o,\eta_e\geq0\), this is equivalent to \[ \boxed{\eta_o=\eta_e=0} \tag{43} \]

Combining this with (42), we obtain the principal result.


Theorem 11 — General necessary-and-sufficient condition for all-negative radicals
For the normalized radical \[R= \sqrt{1-\gamma_1\sqrt{1-\gamma_2 \sqrt{1-\gamma_3\cdots}}}, \qquad 0 \lt \gamma_n\leq1,\] define \(a_k=\gamma_{2k-1}\), \(b_k=\gamma_{2k}\), and the quantities in (37)–(38). Then \[ \boxed{ \begin{aligned} R\text{ converges}\iff{}& S_o=+\infty\\ &\text{or }S_e=+\infty\\ &\text{or }(\eta_o=0\text{ and }\eta_e=0). \end{aligned} } \tag{44} \] Equivalently, \[ \boxed{ \begin{aligned} R\text{ diverges}\iff{}& S_o \lt \infty,\quad S_e \lt \infty,\\ &\text{and }(\eta_o>0\text{ or }\eta_e>0). \end{aligned} } \tag{45} \]
Boundary cases
The preceding proof used the assumption that both parity classes contain infinitely many coefficients below one.
If the odd coefficients are eventually all one, Theorem 8 gives \[R\text{ converges} \iff S_e=+\infty\] This agrees with (44), because then \(\eta_o=+\infty\).
Similarly, if the even coefficients are eventually all one, Theorem 9 gives \[R\text{ converges} \iff S_o=+\infty\] If both parity classes are eventually all one, both series are finite and both deficit measures are infinite, so the radical diverges.
Thus Theorem 11 covers every sequence in the normalized class \(0 \lt \gamma_n\leq1\), including all boundary cases.

\(\square\)

PART IX. The general theorem in a compact single-energy form

The general criterion can be compressed into one scalar quantity constructed from the log-odds of the coefficients.


22. Weighted log-odds
Define \[\lambda_n=\log\frac{\gamma_n}{1-\gamma_n}\] For any real \(x\), write \[x^+=\max(x,0), \qquad x^-=\max(-x,0)\] Define the negative energy \[ \boxed{\mathcal N=\sum_{k=1}^{\infty} 2^{-k} \left[(\lambda_{2k-1})^-+(\lambda_{2k})^-\right]} \tag{46} \] Define the positive barrier \[ \boxed{\mathcal D=\liminf_{k\to\infty}2^{-k}(\lambda_{2k-1})^+ + \liminf_{k\to\infty}2^{-k}(\lambda_{2k})^+} \tag{47} \] Finally, define \[ \boxed{\mathcal H=\mathcal N+\frac1{\mathcal D}} \tag{48} \] We adopt the conventions \[\frac10=+\infty,\qquad \frac1{+\infty}=0\] Theorem 12 — Single weighted-energy criterion
The all-negative normalized radical converges if and only if \[\boxed{\mathcal H=+\infty}\]

Proof
The two identities \[\log\frac1\gamma = \log(1+e^{-\lambda})\] and \[\log\frac1{1-\gamma} = \log(1+e^\lambda)\] show that \[\log\frac1\gamma-\lambda^-\] and \[\log\frac1{1-\gamma}-\lambda^+\] are each between zero and \(\log2\).
After multiplication by the geometric weights, these bounded differences do not affect convergence of the series or the values of the parity-wise lower limits.
Therefore, \[\mathcal N \lt \infty \iff S_o \lt \infty\text{ and }S_e \lt \infty, \] and \[\mathcal D=0 \iff\eta_o=\eta_e=0\] The result follows directly from Theorem 11.

\(\square\)

Interpretation
The negative energy measures the accumulated effect of small coefficients.
The positive barrier measures whether either parity remains persistently close to one on the critical exponential scale.
The classification is: \[ \begin{array} \text{Negative energy } \mathcal N\ & \text{Positive barrier } \mathcal D & \text{Result} \\ \text{Infinite} & \text{Any value} & \text{Converges} \\ \text{Finite} & \text{Zero} & \text{Converges} \\ \text{Finite} & \text{Positive} & \text{Diverges} \\ \end{array} \] The two parity-wise lower limits must remain independent. Replacing them by a single synchronized lower limit is not generally valid.

PART X. Important consequences of the arbitrary-sequence theorem
23. Near-critical coefficients
Suppose \[\gamma_n\longrightarrow1\] Then both weighted logarithmic series \(S_o,S_e\) are finite, because \[\log\frac1{\gamma_n}\longrightarrow0\]

The general theorem therefore reduces to a particularly elegant condition.


Theorem 13 — Near-critical convergence criterion
If \(\gamma_n\to1\), then \[ \boxed{ \begin{aligned} R\text{ converges}\iff{}& \liminf_{\substack{n\to\infty\\n\text{ odd}}}\frac{\log(1/(1-\gamma_n))}{2^{n/2}}=0\\[1mm] &\text{and}\\[1mm] &\liminf_{\substack{n\to\infty\\n\text{ even}}}\frac{\log(1/(1-\gamma_n))}{2^{n/2}}=0. \end{aligned} } \tag{49} \] Thus, on each positional parity, there must be arbitrarily deep coefficients whose departure from one is sufficiently large relative to their depth.
The two parities need not achieve this at the same indices.

24. The critical exponential family
Consider \[ \boxed{\gamma_n=1-\exp(-Mc^n),\qquad M>0,\quad c>0} \tag{50} \] Then \[\log\frac1{1-\gamma_n}=Mc^n\] For \(c>1\), applying Theorem 13 gives \[\frac{Mc^n}{2^{n/2}} = M\left(\frac c{\sqrt2}\right)^n\] For \(0 \lt c\leq1\), the general theorem gives convergence directly.
Combining the cases, \[ \boxed{ \begin{cases} 0 \lt c \lt \sqrt2 &: \text{converges},\\ c=\sqrt2 &: \text{diverges},\\ c>\sqrt2 &: \text{diverges}. \end{cases} } \tag{51} \] The critical value is exactly \(\sqrt2\).
The borderline deserves particular attention: even when \(M\) is arbitrarily small, the sequence with \(c=\sqrt2\) diverges. The uncertainty can be extremely small, but it does not disappear.

25. Infinitely many isolated subcritical coefficients

A useful corollary of Theorem 11 is the following.


Corollary 2 — Sparse subcritical coefficients
Suppose there is a fixed \(\rho \lt 1\) such that \[\gamma_n\leq\rho\] for infinitely many odd positions and infinitely many even positions.
Then the infinite radical converges.

Proof
On each of the two infinite subsequences, \[\log\frac1{1-\gamma_n} \leq \log\frac1{1-\rho}\] The corresponding geometrically weighted lower limits are therefore zero.
The result follows from Theorem 11.

\(\square\)

For example, consider \[ \boxed{ \gamma_n= \begin{cases} \rho,&n\text{ is a perfect square},\\ 1,&\text{otherwise}, \end{cases} \qquad 0 \lt \rho \lt 1. } \tag{52} \] There are infinitely many odd squares and infinitely many even squares. Consequently, both parity-wise deficit lower limits are zero.
The radical converges, despite the coefficients being equal to one at almost every position.
This is a particularly interesting non-periodic example.

26. An asymmetric mixed-coefficient example
Consider the sequence \[ \boxed{ \begin{aligned} \gamma_{2k-1}&=1-e^{-4^k},\\ \gamma_{2k}&=e^{-2\cdot4^k}. \end{aligned} } \tag{53} \] The odd coefficients are extraordinarily close to one, while the even coefficients are extraordinarily close to zero.
For the even-position series, \[ \begin{aligned} S_e &=\sum_{k=1}^{\infty} 2^{-k}\log\frac1{e^{-2\cdot4^k}}\\ &=\sum_{k=1}^{\infty}2^{-k}(2\cdot4^k)\\ &=+\infty. \end{aligned} \] Therefore the radical converges, irrespective of the odd-position behaviour.
This illustrates an important feature of the general theorem: a sufficiently strong accumulation of small coefficients on just one parity can guarantee convergence.

PART XI. Consolidated results

The following tables collect the main milestone theorems.


Radical with all positive signs
\[ \begin{array} \text{Coefficient pattern} & \text{Necessary-and-sufficient condition} \\ \text{Arbitrary} a_n\geq0 & \sup_n a_n^{1/2^n} \lt \infty \\ \text{Arbitrary} a_n,b_n>0 & \text{Herschfeld condition after rescaling, equation (2)} \\ \end{array} \] Radical with all negative signs
\[ \begin{array} \text{Coefficient pattern} & \text{Necessary-and-sufficient condition} \\ \text{Constant coefficient} a & a \lt 1 \\ \text{Period 2} & \text{Both coefficients below one} \\ \text{Period 3} & \text{At least one coefficient below one} \\ \text{Any odd period} & \text{At least one coefficient below one} \\ \text{Any even period} & \text{At least one coefficient below one on each parity} \\ \text{Odd coefficients eventually one} & S_e=+\infty \\ \text{Even coefficients eventually one} & S_o=+\infty \\ \text{Arbitrary coefficients} & \text{Theorem 11, equation (44)} \\ \text{Coefficients approaching one} & \text{Theorem 13, equation (49)} \\ \end{array} \]

PART XII. Overall mathematical conclusions
The investigation has produced three particularly important insights.

1. The positive and negative cases are fundamentally different
For positive nested radicals, convergence is controlled by the individual terms and their growth on the scale \(2^n\).
For negative nested radicals, the problem is controlled by two-level transformations. Their repeated action produces the critical scale \(2^{n/2}\).

2. The odd/even distinction is intrinsic
For periodic sequences:
- An odd period interchanges the two positional parities after one period. A single subcritical coefficient is enough.
- An even period preserves the positional parities. A subcritical coefficient is required on each parity.
For arbitrary sequences, the same distinction survives as two independent parity-wise lower-limit conditions.

3. The arbitrary-sequence problem has a coefficient-only solution
The main result is Theorem 11: \[ \boxed{ \begin{aligned} R\text{ converges}\iff{}& \sum_{k=1}^{\infty}2^{-k}\log\frac1{\gamma_{2k-1}}=+\infty\\ &\quad\text{or}\\ &\sum_{k=1}^{\infty}2^{-k}\log\frac1{\gamma_{2k}}=+\infty\\ &\quad\text{or}\\ &\left[\liminf_{k\to\infty}2^{-k}\log\frac1{1-\gamma_{2k-1}}=0\right.\\ &\qquad\left.\text{and }\liminf_{k\to\infty}2^{-k}\log\frac1{1-\gamma_{2k}}=0\right]. \end{aligned} } \] This condition does not require periodicity, monotonicity, positive density of subcritical coefficients, or convergence of the coefficient sequence.
It covers the full normalized range \[0 \lt \gamma_n\leq1\] The case \(\gamma_n>1\) is not covered: then real-valuedness depends on the actual subsequent tail values, and a separate analysis is needed.

Wednesday, 22 August 2018

Hands on a clock

A simple mathematical problem today, and three solutions. 

Problem
On a wall clock, the hour hand and the minute hand coincide at noon, and at about five minutes past one, and ten past two, and so on. But if you look closely, at ten minutes past two, the hour hand is a little ahead of the minute hand, and they actually coincide a small bit later.




When exactly do the two hands meet?

Solutions
Below are three solutions. The first solution outlines the first approach taken by most adults to think about the problem. The second solution is closer to how a middle school student might solve it, and gives a more general answer. The third solution is more intuitive, and provides deeper insights into the inner workings of the previous solutions, and to the problem itself.

Solution 1 - Geometric progression
It takes twelve hours for the hour hand to complete a revolution on the dial, and the minute hand makes twelve revolutions during that time. Thus, for every revolution of the minute hand, the hour hand makes a twelfth; or, to break it down further, the hour hand moves a twelfth of the "clock distance" that the minute hand does in any time interval.
So, in the ten minutes since the clock struck two, the hour hand has moved ahead by a twelfth of these "ten minutes", which is the gap visible between the hands in the picture above. The minute hand covers this gap in a twelfth of ten minutes, but by this time, the hour hand has moved by a "clock distance" which is a twelfth of that, and created another, even smaller, gap. By the time the minute hand covers that gap, the hour hand will have again moved ahead by an even smaller amount (a twelfth), and so on.

Thus, T, the total time taken by the minute hand to catch up, is found by adding all these times to cover the gaps:

T = (1/12)*10 + (1/12)*(1/12)*10 + (1/12)*(1/12)*(1/12)*10 + ...

Multiplying both sides by 12, we get

12T = 10 + (1/12)*10 + (1/12)*(1/12)*10 + ...

or,

12T = 10 + T

i.e.

T = 10/11

Thus, the minute hand catches up with the hour hand in 10/11 minutes, or about 54.5 seconds. The two hands meet at approximately ten minutes and 54.5 seconds past two. To be exact, they meet at 10 + 10/11 = 120/11 minutes past two, or an eleventh of two hours past two.

Solution 2 - Algebraic approach
Say the current time is h hours and m minutes, where h is a natural number in [0, 11] and m is a real number in [0, 60). In m minutes, the minute hand covers m/60 of its revolution. The hour hand had already covered h/12 of its revolution when the time was h hours and 0 minutes, and since then, it has further moved a twelfth of the "clock distance" covered by the minute hand in m minutes i.e. (1/12)*(m/60). (For illustration, the picture above shows the scene for h = 2 and m = 10.)

Thus, for the two hands to coincide,

m/60 = h/12 + (1/12)*(m/60)

i.e.

h/12 = (11/12)*(m/60)

or,

m = (60/11)*h

For h = 2, m becomes 120/11 minutes, the same value as seen earlier, but this formula also lets us see all the other times when the hands meet, by putting in all the values of h. For example, for h = 0, m becomes 0 which is simply when the clock strikes twelve; for h = 6, m becomes 360/11 i.e. the hands meet at about 32 minutes and 48.6 seconds past six. Also, for h = 11, m becomes 60, so the hands meet at 60 minutes past eleven, which is simply at twelve, the same value as given by h = 0.

Solution 3 - Physical reasoning
Since the two hands have a constant angular speed, their relative angular speed must be constant as well. This means that if the angle between them at time T is A, and at T + t is A + a, then the angle between them at time T + 2t must be A + 2a. A special case of this is when a = 0 (or a multiple of 360 degrees). Thus, if the angle between the two hands at time T is the same as at time T + t, then it must also be the same as at time T + 2t, and at T + 3t, and so on. Conversely, if the angle at time T repeats k times until time T + kt, then those k times must be T + t, T + 2t, ..., T + kt.

Now, it is also easy to see that after 12 noon, the two hands coincide again 11 times until midnight viz. at about 01:05, about 02:11, and so on to about 10:54, and finally again at 12:00. Thus, by above reasoning, the two hands must coincide in every 12/11 hours, or every 1 + 1/11 hour. The second meeting after 12 should occur in 2 + 2/11 hours i.e. an eleventh of two hours after two, which is the same value that we saw in the previous solutions.

This reasoning applies for any angle between the two hands. Since the speeds are constant, for any time interval t, the angle at 12:00 + t must be the same as 12/11 hours + t later, and thus, any angle made between the two hands must repeat every 12/11 hours.
When are the hands exactly opposite? They oppose each other at exactly 6:00, and so they must oppose each other every 12/11 hours after that. At 12:30, they are just short of opposite, but by how much? 6 times 12/11 hours tells us that they oppose each other at 32 + 8/11 minutes past six. Similarly, when do the hands make a right angle? They do at 3:00 and 9:00, so we can keep on adding 12/11 hours to these times to find all the other times.

Sunday, 22 March 2015

Sea shells of Maths


I have loved Mathematics ever since I can remember - its interesting patterns, astonishing results, and elegant proofs. As a kid, I spent a lot of time playing with numbers, finding more and more silly patterns, and looking for the rules that would explain them. I would spend hours at end on my explorations, like a child trying to collect the prettiest sea shells on the beach.

The more I learnt, the more I wanted to explore, but I never really dived into the depths; I just waded as deep as my basic education would let me. And to this day, I'm still the child who gets excited by pretty sea shells on the shore of Mathematics. Let me show you a typical sea shell I found the other day, but first I'll tell you the story of how I found it.

It's a long story, which begins when I was checking some calculations and computed, among other things, the squares of 119 and 169. I noticed that 1192 + 1202 = 1692, and I started thinking about other such examples.

One generalization is of course Pythagorean triplets

a2 + b2 = c2

and we already know how to generate them using

a = m2 - n2, b = 2mn, c = m2 + n2

For m = 12, n = 5, we get our equation above.

But I was now considering another possible generalization, of this form:

Sum of (m + 1) consecutive squares on the left side equals sum of m consecutive squares on the right. Some examples:

For m = 1:

202 + 212 = 292
1192 + 1202 = 1692

For m = 2:

1082 + 1092 + 1102 = 1332 + 1342

For m = 3:

212 + 222 + 232 + 242 = 252 + 262 + 272

A further generalization is to take squares with a constant difference d, instead of consecutive squares. Some examples:

For d = 2, m = 3:

92 + 112 + 132 + 152 = 122 + 142 + 162
1652 + 1672 + 1692 + 1712 = 1922 + 1942 + 1962

For d = 5, m = 2:

82 + 132 + 182 = 142 + 192

A little investigation shows that given any m and d, there is a solution for every integer p such that m(m + 1)p(p + d) is a square. For the case where d = 1 i.e. for consecutive squares, this means that given any m, there is a solution for every integer p such that the product of mth and pth Triangular numbers is a Square. How pretty is that!

We get the following method to generate the actual solution which, by the way, is how I found the examples above:

Let r = p(m + 1), s = m(p + d), and z = gcd(r, s)
Let a = sqrt(r/z), b = sqrt(s/z)
Let k = zb(a + b) - md, n = za(a + b)

Then the sum of squares of the (m + 1) numbers


k, k + d, k + 2d, ..., k + md

equals the sum of squares of the m numbers


n + d, n + 2d, ..., n + md

So, for example, d = 2, m = 15, p = 3 gives us that the sum of squares of odd numbers from 105 to 135 equals the sum of squares of even numbers from 110 to 138.
Also, d = 1, m = 1, p = 49 gives us the equation we started with, 1192 + 1202 = 1692.

And this finally brings us to the sea shell that I was talking about.
For d = 1, and for any m, putting p = m gives us:

The sum of first (m + 1) squares starting at m(2m + 1) equals the sum of next m squares.

Thus, for m = 1, we get
32 + 42 = 52

For m = 2,
102 + 112 + 122 = 132 + 142

For m = 3,
212 + 222 + 232 + 242 = 252 + 262 + 272

For m = 4,
362 + 372 + 382 + 392 + 402 = 412 + 422 + 432 + 442

For m = 5,
552 + 562 + 572 + 582 + 592 + 602 = 612 + 622 + 632 + 642 + 652

And so on, ad infinitum.
That's a nice little sparkling sea shell, isn't it? :)

PostScript

While looking at the equation 1192 + 1202 = 1692, I remembered that 82 + 152 = 172, and I realized that I could rewrite the above equation in a more pleasing form, as

(72x82) + (82x152) + (152x72) = (132x132)

Why do I like it? Because it is of the form

(a x b) + (b x c) + (c x a) = (d x d)

where a, b, c, and d are squares of integers! The left hand side of this equation has a sweet symmetry, and I'm a total dope for symmetry. A friend pointed out that we could just take square root on both sides, and get

72 + 82 + 7x8 = 132

and that using the same idea as above, we can actually write

72 + 82 + 7x8 = 32 + 42 + (3x4)2

which was unexpected to me, and not as pleasing; I felt that it was not as aesthetically neat as the previous one. Beauty lies, my friend reminded me, in the eyes of the beholder.

Monday, 22 July 2013

Generating list of primes


I thought I'd share some basic ideas to make faster codes for some simple problems. One simple problem every post.

Generating list of all primes less than or equal to N

Simple enough problem, and I'm sure that Googling it will probably yield a host of solutions, but let's try coming up with a basic solution ourselves. So, to get started, a brute force solution would be to check divisibility of every number by numbers smaller than it.
This is Solution 0, which in C++ looks like this :-

vector <int> Primes;
for( int i = 2 ; i <= N ; i++) {
      bool isPrime = true;
      for( int j = 2 ; j < i ; j++)
            if( i % j == 0 ) {
                  isPrime = false;
                  break;
            }
      if( isPrime ) Primes.push_back( i );
}

On my poor decade-old computer (2.x GHz, 500MB RAM), when compiled with "gcc -O2", the above code takes 7s for N = 10^5. That is a crappy solution. We can improve it a lot.

To make it faster, we can ignore the even numbers and concern ourselves with just the odd numbers, but that only makes it slightly faster.
(Why only slightly faster? Aren't we removing half the numbers? Well yes, but it's not like an equal amount of time is spent on every number. Even numbers get discarded very quickly in the inner loop, the almost-primes take a lot more time to discard, and the primes take the most amount of time to confirm that there are no divisors.)
Also, since we are generating and saving a list of primes, we can use this list to speed things up - we don't need to divide by every single number but just smaller primes.
So we have Solution 1, which in C++ looks like this :-

vector <int> Primes;
Primes.push_back( 2 );
for( int i = 3 ; i <= N ; i += 2 ) {
      bool isPrime = true;
      for( vector <int> :: iterator j = Primes.begin() + 1 ; j != Primes.end() ; j++ )
            if( i % *j == 0 ) {
                  isPrime = false;
                  break;
            }
      if( isPrime ) Primes.push_back( i );
}

If we compare the run-times, we get:
N = 10^5N = 10^6
Solution 07s~12 min
Solution 10.7s~48s
This code is faster than the previous one, but this is still a terrible solution.

The above two solutions are very slow because their time complexity is essentially quadratic in N. (Actually, other than N^2, we also have some complicated terms of log(N) here, but the basic idea is that for every number, we are checking with all the primes smaller than it, which is (sort of) as bad as two loops of N).
This can be easily improved, since we only need to check with primes smaller than the square root of a number e.g. to check whether 101 is a prime, we only need to check with all primes up to 10 i.e. 2, 3, 5 and 7.
This gives us Solution 2, for which the C++ code is the same as above, except this line :

for( vector <int> :: iterator j = Primes.begin() + 1 ; j != Primes.end() && *j * *j <= i ; j++ )

Now we get:
N = 10^5N = 10^6N = 10^7N = 10^8
Solution 07s~12 min
Solution 10.7s~48s
Solution 20.2s4.5s~100s
The run-times show a sudden improvement as the time complexity comes down by a factor of N^1/2. (The asymptotic time complexity is an even more complicated expression now, and I'm not even gonna look into it now).

Now, how do we make this faster? Well, to reduce time from Solution 0 to Solution 2, instead of dividing by every smaller number, we were dividing only by primes smaller than the square root. But why go through this entire list every single time? I mean for every single number we first divide by 3, then 5, then 7, then 11, and so on until we find a divisor. For a number like 391 = 17*23, 5 iterations (3, 5, 7, 11, 13) are tried before the sixth iteration (17) marks this number as composite. Can't we save this effort? Isn't there any easier way to directly jump to its divisors 17 and 23?
Well, not really. It is a hard problem to find the factors of a given number. But we can approach this from another direction. It may be difficult to find divisors of a given number but it is easy to find multiples of a given divisor. For every prime number we find, we can find all its multiples in a single loop and discard these numbers as composite. Thus, now, to eliminate 391 = 17*23, we save the time of unnecessarily checking it with 3, 5, 7, 11 and 13 before it is eliminated by 17. As there are a lot of composite numbers to eliminate, this makes it considerably faster.
This solution is basically Sieve of Eratosthenes which was taught to us in middle school.




Our Solution 3 looks like this in C++ :-

vector <int> Primes;
Primes.push_back( 2 );
vector <bool> Sieve( N + 1 );
for( int i = 3 ; i <= N ; i += 2 ) Sieve[i] = 1;
for( int i = 3 ; i <= N ; i += 2 )
      if( Sieve[i] ) {
            Primes.push_back( i );
            for( int j = 3 * i ; j <= N ; j += 2 * i ) if( Sieve[j] ) Sieve[j] = 0;
      }

Note how we are still ignoring all the even numbers in our solution. Unlike our first solution, this actually makes a non-negligible difference right now. This is because unlike our first solution, the overhead involved with discarding each composite number is much lower, and getting rid of half the numbers makes it almost twice as fast.
Now we get:
N = 10^5N = 10^6N = 10^7N = 10^8N = 10^9
Solution 07s~12 min
Solution 10.7s~48s
Solution 20.2s4.5s~100s
Solution 30.2s4.2s~60s

Now, how do we make this faster? Well, earlier in Solution 2, when we were checking divisibility by 2, 3, 5, 7 etc we noted that we only needed to check up to the square root of the number. Along similar lines of reasoning, we note that when we are discarding multiples of a prime p, we only need to consider the multiples greater than or equal to p^2, since the ones below have already been discarded by smaller primes.
This gives us our Solution 4, which in C++ looks the same as the previous one, the only change being inside this if block :

if( Sieve[i] ) {
      Primes.push_back( i );
      if( 1LL * i * i > N ) continue;
      for( int j = i * i ; j <= N ; j += 2 * i ) if( Sieve[j] ) Sieve[j] = 0;
}

Now we get:
N = 10^5N = 10^6N = 10^7N = 10^8N = 10^9
Solution 07s~12 min
Solution 10.7s~48s
Solution 20.2s4.5s~100s
Solution 30.2s4.2s~60s
Solution 40.14s2.4s~28s

Now, the same question that we ask each time : how do we make this faster? Consider what happens when we discard multiples of 23. We start at 23x23, then 23x25, then 23x27, and so on. However, after 23x23, many of its multiples have already been discarded by smaller primes. 23x25 is discarded by 5, 23x27 by 3, 23x33 by 3, 23x35 by 5 and so on. So we could potentially save some time if we only focus on its multiples which have not already been discarded.These are numbers which are only divisible by 23 and larger primes.
This gives us our Solution 5, which in C++ looks like this :-

vector <int> Primes;
Primes.push_back( 2 );
vector <bool> Sieve( N + 1 );
for( int i = 3 ; i <= N ; i += 2 ) Sieve[i]=1;
for( int i = 3 ; i <= N ; i += 2 )
      if( Sieve[i] ) {
            Primes.push_back( i );
            if( 1LL * i * i > N ) continue;
            for( int j = N / i ; j >= i ; j-- ) if( Sieve[j] ) Sieve[i * j] = 0;
      }

Now we get:
N = 10^5N = 10^6N = 10^7N = 10^8N = 10^9
Solution 07s~12 min
Solution 10.7s~48s
Solution 20.2s4.5s~100s
Solution 30.2s4.2s~60s
Solution 40.14s2.4s~28s
Solution 52s~21s

Now, how do we make this faster? I'll continue this in Part 2.

Wednesday, 27 March 2013

Casablanca


Have you seen Casablanca ?

Classic Hollywood 1942 movie starring Humphrey Bogart and Ingrid Bergman. Definitely on any top 10 movie site. Simple plot, great actors, nice ending. Often been borrowed from, and its dialogues been referred to for decades after.

Bogart and Ingrid have a fabulous and rare chemistry, and Bogart's cold, cynical character has awesome witty dialogues - you can read nearly half the movie if you go to IMDB Memorable Quotes. Who hasn't heard the now-a-classic line "Play it Sam. Play As Time Goes By" ? And who can forget "Of all the gin joints ..." ?

Even the minor characters, played by actors like Peter Lorre and, especially, Claude Reins, are superb. ( "I think this is the beginning of a beautiful friendship ..." )

Well, all that is very well, but those are not the reasons I'm writing about Casablanca. My reason is Ingrid Bergman.

I swear, Ingrid in Casablanca is the most gorgeous woman I've ever seen on television.

Ingrid was a beautiful woman, no doubt, but in this movie she's just awesome. No other photograph, no other movie of her even comes close to her looks in this movie. And I don't mean that she wears a hot dress in this movie or anything like that; she just looks oh so beautiful. Every time I've seen the movie, every single time, just as soon as she entered the screen, I breathed "Wow!"

"Here's looking at you, kid !"


It's a good movie. If you haven't seen the movie, you might want to.
A Franc for your thoughts ?

p.s. It goes like
( Ilsa, to a pensive Rick: A Franc for your thoughts ?
Rick: In America they'd bring only a penny, and, huh, I guess that's about all they're worth.
Ilsa: Well, I'm willing to be overcharged. )

Saturday, 3 May 2008

Arbit 2


In one of my internship interviews, I was asked a puzzle that I took over 10 minutes to answer:

"There are 100 prisoners about to be executed the next morning, in the following fashion - they are standed in a queue, and on every head a hat is placed, either white or black. (Number of white or black hats not known in advance). Now, starting from the last person, prisoner#100 to prisoner#1, each one says a colour of these two. (Every one can only see all the people in front but can hear what any person says.) Then only the prisoners who guessed their hat's colour correctly, survive. Rest die. They are told this the night before; come up with a strategy that saves as many of them as possible."

I started thinking with the easiest solution - even numbered person speaks the colour of the person in front, who repeats what they just heard. This way, 50 people definitely live, others have a 50-50 chance, so expected number of survivors is 75. But this was just the first thought, this can obviously be greatly improved.

( Solution follows this, so if you wanna think on your own first, do so before reading further. )

The solution I finally gave was that the prisoner#100 counts the white hats she can see, and says white if the number's even and black if it's odd. Prisoner#99 now counts the white hats she can see, and if her count is same (odd/even) as prisoner#100's count (odd/even), her hat must be black, otherwise white. So she says the colour of her hat. Prisoner#98 now counts the white hats (counts prisoner#99's hat too if it was white), compares this value with prisoner#100's count, and by same reasoning gets her colour. And so on to the first prisoner, who will only consider the colours of prisoners 99 to 2 when counting hats, and by same logic gets her colour.

So, the first 99 people definitely survive, and the last person has a 50-50 chance.

So far, so good. But later, after the interview, I started thinking, what if there were not 2 types of hats, but three - red, blue and green? Can the solution be modified to still save 99 people? What if there were n types of hats? Can 99 people be saved then? I found that a simple generalization serves the purpose.

( Again, if you want to think on your own, do so before reading further. )

Lets start with 3 colours of hats - Red, Blue and Green.
Prisoner#100 counts number of red hats (r) and the number of blue hats (b), and calculates m100 = (2*r + b) mod 3 . She then says R, B or G depending on whether m100 is 0, 1 or 2 respectively. Note that depending on this colour, everyone now knows m100. Prisoner#99 now counts hats and finds m99 = (2*r + b) mod 3. Now her colour is R, B or G if (m100-m99) mod 3 is 2, 1 or 0 respectively. Again, prisoner#98 counts hats, also considers prisoner#99's colour, then finds (m100-m98) mod 3, and by same reasoning finds her colour. And so on until the first person.

Just as before, first 99 prisoners live, and the last person has a 1 in 3 chance.

Similarly, for n colours - C1, C2... Cn. We just generalise this process.
Prisoner#100 counts numbers of hats of colour C1(r1), number of hats of colour C2(r2) and so on till Cn-1 (rn-1), and finds m100 = { (n-1)*r1+(n-2)*r2+... 1*rn-1 } mod n. She then says C1, C2... or Cn-1 if m100 is 0, 1, 2 .. or n-1 respectively. Prisoner#99 now counts hats and finds m99, and her colour is C1, C2... or Cn if (m100-m99) mod n is n-1, n-2 ... or 1 respectively. Again, prisoner#98 counts hats, also considers prisoner#99's colour, then finds (m100-m98) mod n, and by same reasoning finds her colour. And so on until the first person.

Once again, first 99 prisoners live, and the last person has a 1 in n chance.

The most interesting aspect of this generalization comes when the number of colours, n, tends to infinite. Just imagine the odds against the 100 men - they all have to guess the colour of their hats when the number of options to choose from is unimaginably huge. Despite the odds, their strategy lets the first 99 prisoners live. But the last person has a 1 in n chance of survival!

So, here's the funny part - infinite colours, yet 99 prisoners guess correctly thanks to the last person, who certainly dies. Funny, huh?

Tuesday, 15 April 2008

Arbit


For my first log, I'll tell ya about something arbitrary that I find cool.
As a child, you must've known the age-old children's puzzle - Draw the following without lifting pen from paper and without repeating any line.
The age old solution is - you fold the paper and use the backside as a bridge to get from one point to another. It's a very general trick, and can be used to draw anything without lifting pen from paper.

Let's look deeper. Using graph theory, it's easy to show that the above figure has no path that uses each edge exactly once. (Just read euler paths on wiki.) The basic idea is that if there's such a path, every time it visits a vertex, it must leave the vertex using a different edge, and so the degree of every vertex must be even, except for the starting and ending vertex (if they are not same), in which case, they both must have odd degrees. In the above figure, the four ends of the square all have odd degrees, which makes it impossible for such a path to exist.

Actually, the above condition on degrees can be shown to be both necessary and sufficient for an Euler path to exist. So, consider the following figure:
(Same as figure 1, except each line is drawn twice.) Clearly, every vertex has even degree, as I just doubled the degree of every vertex. So, this figure has an Euler cycle.

This gives us a new solution to the age-old problem of drawing figure 1. You draw figure 2 instead, and then use the axiom - "What I can do twice, I can do once" ! Neat huh? My new solution too is a general trick; it can be used to draw anything connected. Ta-da!