ireducible polynomials with coefficients in $\{0,-1\}$

163 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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)