1
$\begingroup$

The following statement about finite differences of the positions of the ordered multiset of factors of $n$ in the sequence of primes seems to be true based on my empirical tests.

Let $n=p_0^{j_0} \ldots, p_i^{j_i}$, where $p_0, \ldots, p_i$ are the prime factors of $n$ in increasing order. Let $[q_0, \ldots, q_m]$ be the list of the positions in the sequence of primes starting with 2 of these factors with their respective multiplicities. Let $[q_1-q_0,\ldots, q_m-q_{m-1}]$ be the list of their consecutive differences, clearly all $\geq 0$. Let $b(x)=\lfloor log_2(x+1) \rfloor$.

Then $b(n) \geq \sum_{l=1}^m b(q_l-q_{l-1})$.

Is this a known result? Does it obviously follow from some known theorem? Can someone point to the best proof techniques to approach this problem?

As an example, the differences between the left and the right side of the inequality on [1..31] are [1,0,2,1,1,0,3,2,2,1,2,1,1,1,4,2,3,1,3,2,2,1,3,3,2,3,2,1,2,1,5,2].

My interest in representing the prime factors of a number through a bijection to the finite differences of their positions in the sequence of primes comes from its use as a succinct representation for the factoring of $n$. Also, if applied recursively, it provides an interesting tree representation of $n$.

Thanks in advance for any hints on this,

Paul Tarau

http://www.cse.unt.edu/~tarau

Improve this question
$\endgroup$
6
  • $\begingroup$ What do you mean exactly with "succinct representation for the factoring of n"? For every succinct representation $r(\cdot)$, and for every m there is a number $n$ whose binary representation has length $m =b(n)$ that is incompressible (i.e. $|r(n)|\geq b(n)$. See Kolmogorov complexity, $\endgroup$
    – Vor
    May 4, 2013 at 21:28
  • $\begingroup$ I don't believe I understand your definitions. Could you, please, illustrate them for $n:=30$ and for $n:=40$ (and/or perhaps for any single integer of your choice). $\endgroup$
    – Włodzimierz Holsztyński
    May 5, 2013 at 0:51
  • $\begingroup$ Let me clarify with an example. Floor(log_2 (x+1)) represents the (bijective base-2) bitsize of a number. We have 360->[2,2,2,3,3,5]->[0,0,0,1,0,1] which is "succinct" in the sense that the sum of the bitsizes of the "canonically represented" factors [0,0,0,1,0,1] is smaller the the bit size of 360, i.e. b(360)=8 and the sum of b(x) for x in [0,0,0,1,0,1] is 2 (or 6 if one counts bitsize 1 for 0). For 40=2*2*2*5->[0,0,0,2] we have the sum of bijective base-2 bitsizes 1 vs. bitsize of 40=5. $\endgroup$
    – Paul Tarau
    May 5, 2013 at 1:37
  • $\begingroup$ The equality between b(n) and the sum on the right side holds indeed for some values of n as expected from the existence of incompressibles. But the strict inequality is likely to hold most of the time as there's loss of information due to the fact that we are not using self-delimiting codes and we ignore delimiting costs for the factors. So it makes sense intuitively that the canonically represented factors' total bitsize is smaller. $\endgroup$
    – Paul Tarau
    May 5, 2013 at 1:45
  • $\begingroup$ @PaulTarau: ok, now it's clear. But it is a kind of cheating, because if you don't take into account the "cost" of delimiting the codes, one can consider valid this simpler representation, too: pick the binary representation of a number, then split it in an "array" assuming that every digit has a one on its left; so 360 = 101101000 becomes [01,0,000]. This representation except for n<2 is strictly "shorter" (in your sense) than b(n). $\endgroup$
    – Vor
    May 5, 2013 at 14:15

1 Answer 1

Reset to default
1
$\begingroup$

After a small rephrasing, here it is together with the proof, hopefully correct.

PROPOSITION:

For $n \in \mathbb{N}$, let $n+1=p_0^{j_0} \ldots, p_i^{j_i}$, where $p_0, \ldots, p_i$ are the prime factors of $n+1$ in increasing order. Let $[q_0, \ldots, q_m]$ be the list of the positions in the sequence of primes starting with $2 $ of these factors with their respective multiplicities. Let $[q_1-q_0,\ldots, q_m-q_{m-1}]$ be the list of their consecutive differences, clearly all $\geq 0$. Let $b(x)=\lfloor log_2(x+1) \rfloor$.

Then $b(n) \geq \sum_{l=1}^m b(q_l-q_{l-1})$.

PROOF:

For $n=0$ equality holds, the list on the right (factoring of $1$) being empty. For $n>0$ observe that
$\sum_{l=1}^m b(q_l-q_{l-1}) = \sum_{l=1}^m \lfloor log_2(1+q_l-q_{l-1}) \rfloor \leq \lfloor \sum_{l=1}^m log_2(1+q_l-q_{l-1}) \rfloor \leq \lfloor \sum_{l=1}^m log_2(q_l) \rfloor$ $= \lfloor log_2(\prod_{l=1}^m q_i) \rfloor \leq \lfloor log_2(\prod_{l=0}^m p_i) \rfloor = \lfloor log_2(n+1)\rfloor$ $= b(n)$

This opens a more general question: what conditions are sufficient for a bijection from $\mathbb{N}$ to finite sequences of $\mathbb{N}$ for a similar property to hold? A necessary one (that the bijection derived from primes satisfies) seems to be that all elements in the sequence corresponding to $n$ are smaller then $n$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why do you have equality in your last step? Shouldn't the product be $(n+1)/q_0$? Gerhard "Ask Me About System Design" Paseman, 2013.05.12 $\endgroup$
    – Gerhard Paseman
    May 13, 2013 at 0:49
  • $\begingroup$ @Gerhard Paseman: Thanks for noticing that - I added the term I was implicitely assuming - the prduct of the primes p_i, which is clearly larger than the product of their positions in the sequence of primes. $\endgroup$
    – Paul Tarau
    May 13, 2013 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.