4
$\begingroup$

I'm interested in the polynomials of the form $x^n -x^{n-1} - b_{n-2}x^{n-2} - \cdots -b_1 x -1$ with the coefficients $b_k$ being either zero or one. The prototype is of course the Golden mean $x^2-x-1$. Is there a known name for such polynomials? I would search for info on them, but can't figure out how to form a reasonable search query.

To tighten things up: I'm interested in the ones that are irreducible with respect to one-another (are prime relative to one-another). As far as I can tell, there are the same number of these as there are irreducible polynomials over $\mathbb{F}_2$ -- OEIS A001037 (should that be obvious?). As far as I can tell, they always have just one real root greater than one. I'm interested in the complex roots, too. Some of these show up in papers on "generalized golden means", typically the all-ones case $x^n -x^{n-1} - \cdots -x -1=0$ or the all-zeros case $x^n -x^{n-1}-1=0$, but its not much enlightening. Another factoid: it seems the real roots are dense in [1,2], considering all such polynomials, taking $n\to\infty$. Is there a generating function? I'm guessing that texts in dynamical systems, chaos theory, fractals, subshifts, maybe number theory might discuss these; but under what name?

EDIT: The context for these polynomials is the iterated Beta Transform. I've written a 105-page tract providing a treatment of the Beta Transform, illustrating the usefulness and central natural of these polynomials. It can be found here: https://linas.org/math/solvit.pdf I still don't "understand them", and find this to be annoying.

$\endgroup$
3
  • $\begingroup$ In my playing around with polynomials like this with all the $b_n=0$, the roots are all close to the $n^{th}$ roots of unity. The roots are roughly in a circle in the complex plane since $x^{n-1}(x-1)=1$. IIRC, Even with $b_n\ne0$, the two highest order terms dominate as $n$ becomes large, so the roots are still roughly arranged in a circle in that case $\endgroup$
    – Andy Walls
    Feb 10, 2018 at 12:02
  • $\begingroup$ Glasser has an approach for finding the roots of the trinomial $x^n-x+t=0$, which you might be able to adapt to the trinomial $x^n-x^{n-1}-1=0$ but you might run into convergence problems with the hypergeometric functions. sciencedirect.com/science/article/pii/S0377042700002879 $\endgroup$
    – Andy Walls
    Feb 10, 2018 at 12:37
  • $\begingroup$ Ah, yes, thank you. I was seeing roots arranged in circles at various radii; (specifically, at a radius of 1 over the real root, in a related one-off problem in which these arise.) I see Glasser invokes the multiplication theorem, which is an old favorite of mine... and might provide the doorway I need. $\endgroup$
    – Linas
    Feb 11, 2018 at 8:28

1 Answer 1

0
$\begingroup$

Not an answer, but here's a MatLab/Octave script to visualize how the roots of $$x^n-x^{n-1}-1 = 0$$ compare to the roots of unity $$x^n-1 = 0$$

N = 10;
% x^n - 1 = 0
eta_poly = [1, zeros(1,N-1), -1];
% x^n - x^(n-1) - 1 = 0
r_poly   = [1, -1, zeros(1,N-2), -1];
eta = roots(eta_poly);
r = roots(r_poly);

% Plot the nth roots of unity and the other polynomial's roots
plot(real(eta),imag(eta),'.',real(r),imag(r),'+');
grid on;

% Sort the roots of unity by their arg() in [0, 2*pi)
ae = arg(eta)+2*pi*(arg(eta)<0);
[s,si] = sort(ae);
eta = eta(si);

% Match the closest roots of unity to the roots in r
% and permute r so that it lines up with the corresponding roots of unity
M = length(eta);
c = eta*ones(1,M)-ones(M,1)*r.';
[w,iw] = min(abs(real(c))+abs(imag(c)));
r = (abs(c) <= max(w))*r;

% What's the difference between the roots of unity and the roots of the
% other polynomial?
d = r-eta
r_d = abs(d)
phi_d = arg(d)
$\endgroup$
2
  • $\begingroup$ The case of $x^n-\sum_{k=0}^{n-1} x^k=0$ is interesting: the zeros approach the unit circle surprisingly slowly as $n\to\infty$. $\endgroup$
    – Linas
    Feb 12, 2018 at 20:01
  • $\begingroup$ Also: for small n, the polynomials, roots are the "silver number", pisot number, tribonacci, tetranacci, etc. and have OEIS A092526 A058265 A109134 A086088 A060006 A293506 A103814 to describe them. $\endgroup$
    – Linas
    Feb 12, 2018 at 20:04

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .