Division algorithm for ordinals: how to solve $\omega^2\cdot 2+\omega\cdot4+5=(\omega\cdot2+3)\cdot\alpha+\beta$

Question

As in the question: I know that there exits $\alpha,\beta$ which solve division with remainder in the ordinals. Anyhow, I do not know how to actually find a solution. The thing I tried is to go by attempts, but without much luck: for instance it seems to me that the "naive" solution one would give without knowing that multiplication is not distributive to the left, $\alpha=\omega,\beta=\omega+5$ is wrong.

Any help would be appreciated

Answer 1

Start by observing the largest term in $\alpha$'s Cantor normal form: $\omega\cdot i$. We have

$$(\omega\cdot2+3)\cdot\omega\cdot i=\omega^2\cdot i$$

and hence $i=2$. What remains is $\omega\cdot4+5$ on the LHS, so we can then see the next term in $\alpha$'s Cantor normal form to be $j$.

$$(\omega\cdot2+3)\cdot j=\omega\cdot(2j)+3$$

We can see that we must have $j=2$. What remains is $2$ on the LHS, and so we have

$$\omega^2\cdot2+\omega\cdot4+5=(\omega\cdot2+3)\cdot(\omega\cdot2+2)+2$$

Overall not too unlike normal division. Just take care of how things multiply and distribute when "subtracting" from the LHS.

Answer 2

For the record here is an explicit algorithm in the spirit of Manolios & Vroon 2005 paper. It assumes we have access to Cantor normal forms, and can perform simpler operations (comparisons, subtractions and multiplications). If you find a reference where such a division algorithm is given, please mention in the comments.

We have $\alpha,\beta$ with $\beta>0$. We want $\gamma,\delta$ with $\alpha=\beta\cdot\gamma+\delta$ and $\delta<\beta$.

The case $\alpha<\beta$ is easy, giving $\gamma=0$ and $\delta=\alpha$.

When $\alpha\geq\beta$, we consider the first blocks in the Cantor normal forms $\alpha=\omega^{\alpha_1}\cdot n_1+\alpha'$ and $\beta=\omega^{\beta_1}\cdot m_1+\beta'$.

If now $\alpha_1>\beta_1$ then $\gamma=\omega^{\alpha_1-\beta_1}\cdot n_1+\gamma'$ with $\gamma',\delta$ obtained from the division of the remainder $\alpha'$ by $\beta$.

If $\alpha_1=\beta_1$ we let $d=\lfloor \frac{n_1}{m_1}\rfloor$ and consider two subcases: if $n_1>d\,m_1$ or $\alpha'\geq\beta'$, we let $\gamma=d$, otherwise we let $\gamma=d-1$ (necessarily $d>1$). Finally we let $\delta=\alpha-(\beta\cdot\gamma)$.

I'll try to update this answer with the missing complexity analysis and references to historic papers.