Timeline for how to prove a conjecture on a "canonical equivalent" of factoring
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2013 at 19:56 | answer | added | Paul Tarau | timeline score: 1 | |
| May 5, 2013 at 15:33 | comment | added | Paul Tarau | @Vor: The main difference is that the representation I am considering is a bijection between N and its finite sequences. So what I would like to find out is if the conjecture follows from an information-theoretical fact like "cheating on the delimiters" or some deep properties of primes are involved. Given that the sequence on the right side can contain only naturals smaller than n, the bijection can recurse as in 2014->2015->[2,3,5]->[[1],[0,0],[0,1]]->[[[0]],[[],[]],[[],[0]]]->[[[[]]],[[],[]],[[],[[]]]] until a total bitsize of 0 is reached. | |
| May 5, 2013 at 14:15 | comment | added | Vor | @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). | |
| May 5, 2013 at 1:45 | comment | added | Paul Tarau | 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. | |
| May 5, 2013 at 1:37 | comment | added | Paul Tarau | 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. | |
| May 5, 2013 at 0:51 | comment | added | Włodzimierz Holsztyński | 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). | |
| May 4, 2013 at 21:28 | comment | added | Vor | 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, | |
| May 4, 2013 at 18:54 | history | edited | Paul Tarau | CC BY-SA 3.0 |
spelling
|
| May 4, 2013 at 18:28 | history | asked | Paul Tarau | CC BY-SA 3.0 |