0
$\begingroup$

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$$

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Jan 15 at 15:49
  • $\begingroup$ @PeterTaylor, yes, but there are other numbers (not $2^ap$) with this properties: $15, 30, 51, 60, 85\dots$ $\endgroup$
    – Denis Ivanov
    Commented Jan 15 at 16:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis Shatrov
    Commented Jan 15 at 16:31
  • $\begingroup$ Yes, precisely. $\endgroup$
    – Peter Taylor
    Commented Jan 15 at 16:32
  • $\begingroup$ @DenisShatrov, could you explain more detailed please? $\endgroup$
    – Denis Ivanov
    Commented Jan 15 at 16:35

1 Answer 1

Reset to default
2
$\begingroup$

$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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you, but how to check (without manual arithmetic) are there such carries? I've found idea only about addition $\endgroup$
    – Denis Ivanov
    Commented Jan 15 at 17:16
  • $\begingroup$ @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. $\endgroup$
    – Peter Taylor
    Commented Jan 15 at 17:27
  • $\begingroup$ @ 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? $\endgroup$
    – Denis Ivanov
    Commented Jan 16 at 6:47
  • $\begingroup$ @DenisIvanov, apparently not. The first counterexample is $P_{50539}$. $\endgroup$
    – Peter Taylor
    Commented Jan 16 at 8:12
  • $\begingroup$ Yes I see, but now I'm confused ( $\endgroup$
    – Denis Ivanov
    Commented Jan 16 at 8:15

You must log in to answer this question.

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