Let $\gamma$ be infinitesimally close to 1 (or more precisely, let $\gamma=1-\epsilon$ and consider this problem for sufficiently small $\epsilon$). Suppose I have two quantities which consist of finite sums of powers of $\gamma$, for example, $a=\gamma+\gamma^4$ and $b=\gamma^2+\gamma^3$. Is there an efficient way to determine which of $a$ or $b$ is greater without doing a binomial expansion? (i.e. decide if $a-b>0$?)
Obviously, if $a$ and $b$ consist of a different number of terms, then whichever has more terms is greater. In this case, however, they both have 2 terms.
One straightforward way to decide which is bigger is to expand:
$$ a=(1-\epsilon)+(1-\epsilon)^4 = (1-\epsilon)+(1-4\epsilon+6\epsilon^2-4\epsilon^3+\epsilon^4)=2-5\epsilon+6\epsilon^2-4\epsilon^3+\epsilon^4$$ $$b = (1-\epsilon)^2+(1-\epsilon)^3=(1-2\epsilon+\epsilon^2)+(1-3\epsilon+3\epsilon^2-\epsilon^3)=2-5\epsilon+4\epsilon^2-\epsilon^3$$
So for sufficiently small $\epsilon$, we get $b<a$ since $4\epsilon^2<6\epsilon^2$.
However, ideally I'd like to implement this on a computer efficiently, and in particular, binomial coefficients can grow quite large and require arbitrary precision arithmetic if the array which decides whether the $i$th power of $\gamma$ is present is large. I was hoping that there would be a straightforward, obvious way to just 'look' at them and decide which is bigger. One constraint I have is that for each $i$, $\gamma^i$ appears in at most one of $a$ or $b$ with coefficient $0$ or $1$.
One result I discovered is that if we start with $\gamma$ and for the $n$th power, add or subtract $\gamma^n$ to bring the current sum closer to $0$, we get the Thue-Morse sequence with the signs. For example:
We start with $\gamma$. Since $\gamma>0$, subtract $\gamma^2$. Since $\gamma-\gamma^2>0$, subtract $\gamma^3$. Since $\gamma-\gamma^2-\gamma^3<0$, add $\gamma^4$ etc. The sequence is $\gamma-\gamma^2-\gamma^3+\gamma^4-\gamma^5+\gamma^6+\gamma^7-\gamma^8-\dots$.
Since the Thue-Morse sequence is easy to compute, I was hoping this would give an easy way to generalize this to comparing arbitrary sums of powers of $\gamma$ by comparing them to the Thue-Morse sequence.
Alternatively, a proof of the Thue-Morse property would be nice, and might give me some insight.