Simple question about 0,1-polynomials

Question

Being interested in these polynomials, would like to clarify one small observation.
Let $n\in\mathbb{N}$ and $P_{n}$ is $0,1$-polynomial whose coefficients are binary digits of $n$.
Let $n$ has prime factorization

$$n = p_{1}^{m_{1}}\cdot p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}$$

Find for each prime factor its binary representation $0,1$-polynomial $P_{p_i}$ and substitute in the factorization formula (with corresponding degrees): $$Q_{n}=P_{p_{1}}^{m_{1}} \cdot P_{p_{2}}^{m_{2}}\cdots P_{p_{k}}^{m_{k}}$$
The question is:

When $Q_{n} == P_{n}$ ?

I discovered that this is true for about half of numbers, and I can’t see any pattern in them.
For example:
$p_2=x, p_3=1+x$
$n=6, p_2 \cdot p_3 = x+x^2==p_6$
$n=9, p_3 \cdot p_3 = 1+2 x+x^2 \neq p_9=1+x^3$

$n=56, Q_{56}=x^3+x^4+x^5==P_{56}$
$n=57, Q_{57}=1+2 x+x^4+x^5 \neq P_{57}=1+x^3+x^4+x^5$

First numbers for which $Q_{n} \neq P_{n}$:
$$9, 18, 21, 25, 27, 33, 35, 36, 39, 42, 45, 49, 50, 54, 55, 57, 63, 65, 66, 69, 70, 72, 75, 77, 78, 81\dots$$

The examples you give can easily be explained by observing that the property always holds for $n$ of the form $2^a p$ when $p$ is prime. Perhaps the easiest characterisation, although maybe not the most useful, is that $Q_n = P_n$ whenever $Q_n$ is a $0,1$-polynomial. — Peter Taylor, Jan 15 '24 at 15:49
@PeterTaylor, yes, but there are other numbers (not $2^ap$) with this properties: $15, 30, 51, 60, 85\dots$ — Denis Ivanov, Jan 15 '24 at 16:24
In other words, $P_n = Q_n$ if no carries occur when calculating the product $p_1^{m_1} \cdot \ldots \cdot p_k^{m_k}$ in binary. — Denis Shatrov, Jan 15 '24 at 16:31

score 2 · Accepted Answer · answered Jan 15 '24 at 16:36

2

$Q_n = P_n$ iff there are no carries when multiplying $p_{1}^{m_{1}}\cdot p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}$ in binary.

Consider $P_a P_b$: if there are no carries in the binary multiplication of $ab$ then each set bit of the product corresponds to a coefficient $1$ in $P_{ab}$ and $P_{ab} = P_a P_b$. But if there are carries then $P_a P_b$ is not a $0,1-$polynomial, and furthur multiplication by polynomials with no negative coefficients cannot restore the property of being a $0,1-$polynomial.

answered Jan 15 '24 at 16:36

Peter Taylor

6,571

Thank you, but how to check (without manual arithmetic) are there such carries? I've found idea only about addition – Denis Ivanov Jan 15 '24 at 17:16
@DenisIvanov, the easy statements are that powers of 2 are irrelevant (because they certainly don't cause carries); the odd part must be squarefree; and if odd primes $p$ and $q$ both occur then $(p-1) + (q-1)$ must also be without carries. – Peter Taylor Jan 15 '24 at 17:27
@ Peter Taylor, thank you! Did I understand correctly that this implies: if $n$ is prime, then its $0,1$-poly can only have $1$ or $2$ roots? – Denis Ivanov Jan 16 '24 at 06:47
@DenisIvanov, apparently not. The first counterexample is $P_{50539}$. – Peter Taylor Jan 16 '24 at 08:12
Yes I see, but now I'm confused ( – Denis Ivanov Jan 16 '24 at 08:15
@DenisIvanov, there are a lot of theorems about polynomial roots and I don't know which you thought was relevant. – Peter Taylor Jan 16 '24 at 08:30

Simple question about 0,1-polynomials

1 Answers1

Linked