Find expansion coefficients for non-integer rational base 'b' that minimize "$\epsilon$-closeness" to a root

Question

For a non-integer rational base b, where b $\in$ (1,2), and the allowed expansion coefficients/symbols are $d_k$ $\in$ {-1,0,1}, it is known that b cannot be a root of the polynomial $\sum_{k=0}^n d_k x^k$. My question relates to how one can determine how "close" b can possibly come in terms of it being a solution to the equation $\sum_{k=0}^n d_k x^k = \epsilon$.

Given a finite terminating expansion in n terms, with known n, and known rational non-integer base b $\in$ (1,2), how can one "efficiently" find the coefficients $d_k$ that minimize the absolute value of $\epsilon$?

Furthermore, if b is not fixed, how can one efficiently find a non-integer rational b, assuming one exists in (1,2), that maximizes the value of this "minimum $d_k$" $\epsilon$ for a fixed n?

This may have practical importance in applications where finite terminating representations of numbers in base b are known to be unique in the purely mathematical sense, but should be chosen carefully in computer applications given practical limitations on machine precision.

Answer 1

Let $P(z) = \sum_{k=0}^n d_k z^k$ be of degree $n$ (so $d_n = \pm 1$). If $b = x/y$ (in lowest terms), we must have $|P(b)| \ge y^{-n}$. This is because $$ y^n P(b) = \sum_{k=0}^n d_k x^k y^{n-k} \equiv d_n x^n \not\equiv 0 \mod y$$ It is possible to have equality, e.g. for $b = 3/2$ with $P(z) = z^5 - z^4 - z - 1$ or $P(z) = {z}^{7}-{z}^{6}-{z}^{4}-{z}^{3}+{z}^{2}+z-1$.

Answer 2

For any number of coefficients $ b_{k} $ and $ x^{k} $ with values from some generating function of $ n $,

we can create a series of polynomials

$$ \sum_{k=1}^{n} b_{k_{n}}x_{n}^{k} = b_{0_{n}} + b_{1_{}}x_{n} + b_{2_{n}}x_{n}^{2} + b_{3_{n}}x_{n}^{3} + ... + b_{k_{n}}x_{n}^{k} = \epsilon_{n} $$

with trivial solutions, and use guassian elimination to determine the minimum value of coefficients $ b_{k} $ for generating function associated with the real cut $ b \in (1,2) $

This way we can find the errors $ \epsilon $ in the solutions for the cut above.

We can then put this polynomial into a composition table of arbitrary size to compute the possible values for $\epsilon_{n} $ for any root by means of the $k^{th}$ difference $\Delta_{k} $ algorithm.

The polynomial for $\epsilon_{n} $ looks like this when you compute the table:

$$ \Delta_{1} = \epsilon_{n} - \epsilon_{n+1} $$

$$ \Delta_{2} = \epsilon_{n} - 2\epsilon_{n+1} - \epsilon_{n+2} $$

$$ \Delta_{3} = \epsilon_{n} - 3\epsilon_{n+1} - 3\epsilon_{n+2} - \epsilon_{n+3} $$

Which can be generalised as a binomial perturbation expansion:

$$ (x - \epsilon)^{n} = C^{n}_{r} \epsilon^{r}x^{n-r} = \frac{n!}{r!(n-r)!} \epsilon^{r} x^{n-r} $$

Which has an approximation to real solutions in a set of $ 2^{n-1} $ partitions with a residue of $ 2^{-n} $

The choice of floating point precision should be chosen by the latter values of the residue and partitions required to compute the array of $ k^{th} $ differences.

For a 64K computer, I would recommend $ n < 6 $.