The extra coefficients
Jun. 18th, 2012 06:55 amMinor note on integer complexity stuff.
OOPS about half an hour later: The coefficients originally listed here are wrong, because I forgot a step in how the coefficients were derived! They were translated by 1 -- i.e. instead of "k+1" I had "k". Fixed now.
Let A_r(x) denote the number of numbers n≤x with δ(n)≤r, and B_r(x) denote how many of these are "leaders".
(Yes, in the paper Josh and I submitted we define it by "δ(n)<r", not "δ(n)≤r". Strictly speaking, I should have a different notation for the latter -- well, we do, we denote it by putting a bar on top of the A or B. But that's inconvenient here, so I'll just say that I mean ≤ rather than <, because it makes the statement nicer. This will only make a difference if r<1, anyway.)
Earlier I stated a conjecture on asymptotics for A_r(x). OK, that's not the most readable form of it. But the point is, it comes from knowing most-efficient factorizations of numbers of defect less than 1. Also the point is, if we write k=⌊r⌋ and s=r-k, then it's of the form C*(k+1)^(k-2)/k!^2 (if you care about A_r) and C*(k+1)^(k-1)/k!^2 (if you care about B_r), where C depends on k and s. (Specifically, for any given value of s, it's a polynomial in k.)
Of course, you might also want to focus on a particular congruence class of the complexity mod 3. In which case, you need numbers of integral defect 0, not just those of defect less than 1. And I hadn't checked those. (You also might want to focus on just some further subset for some reason, so you want to know all the individual coefficients, not just their running totals that yield the C's.)
Thing is there are infinitely many. So like, I had checked earlier that 3^n+1 is always "m-irreducible" (meaning it can't be factored most-efficiently) for n≥4. But what about, say, 2(3^n+1)? Is writing it that way necessarily the only way to factor it (most-efficiently) into m-irreducibles? As Juan Arias de Reyna has pointed out, such factorizations are not necessarily unique in general.
Anyway so yesterday I sat down and did the verification -- it's not hard. Yes, 2*3^n+1 is m-irreducible for n≥1 (strictly speaking for n=0 as well but since that yields 3 I'm going to ignore that for now[0]), 4*3^n+1 is for n≥0; and 2(3^n+1), 2²(3^n+1), 2(2*3^n+1) are all the unique ways of factoring those numbers into (non-3) m-irreducibles (for n≥4, n≥4, and n≥1 respectively). And so we get coefficients of k+1, k+1, (k+1)^2, (k+1)*(k+2 choose 2), and (k+1)^2, repsectively. (While 56, 1024, and 112 yield coefficients of (k+1)*(k+3 choose 3), (k+10 choose 10), and k*(k+4 choose 4).)
Or, I mean, those are the coefficients they should yield, if I'm right about how all this works. But they work as an upper bound and I guess that's the important part...
-Harry
[0]There's a good reason for this which I won't explain now but if you understand where this numerical conjecture is coming from at least the ad-hoc reason should be clear.
OOPS about half an hour later: The coefficients originally listed here are wrong, because I forgot a step in how the coefficients were derived! They were translated by 1 -- i.e. instead of "k+1" I had "k". Fixed now.
Let A_r(x) denote the number of numbers n≤x with δ(n)≤r, and B_r(x) denote how many of these are "leaders".
(Yes, in the paper Josh and I submitted we define it by "δ(n)<r", not "δ(n)≤r". Strictly speaking, I should have a different notation for the latter -- well, we do, we denote it by putting a bar on top of the A or B. But that's inconvenient here, so I'll just say that I mean ≤ rather than <, because it makes the statement nicer. This will only make a difference if r<1, anyway.)
Earlier I stated a conjecture on asymptotics for A_r(x). OK, that's not the most readable form of it. But the point is, it comes from knowing most-efficient factorizations of numbers of defect less than 1. Also the point is, if we write k=⌊r⌋ and s=r-k, then it's of the form C*(k+1)^(k-2)/k!^2 (if you care about A_r) and C*(k+1)^(k-1)/k!^2 (if you care about B_r), where C depends on k and s. (Specifically, for any given value of s, it's a polynomial in k.)
Of course, you might also want to focus on a particular congruence class of the complexity mod 3. In which case, you need numbers of integral defect 0, not just those of defect less than 1. And I hadn't checked those. (You also might want to focus on just some further subset for some reason, so you want to know all the individual coefficients, not just their running totals that yield the C's.)
Thing is there are infinitely many. So like, I had checked earlier that 3^n+1 is always "m-irreducible" (meaning it can't be factored most-efficiently) for n≥4. But what about, say, 2(3^n+1)? Is writing it that way necessarily the only way to factor it (most-efficiently) into m-irreducibles? As Juan Arias de Reyna has pointed out, such factorizations are not necessarily unique in general.
Anyway so yesterday I sat down and did the verification -- it's not hard. Yes, 2*3^n+1 is m-irreducible for n≥1 (strictly speaking for n=0 as well but since that yields 3 I'm going to ignore that for now[0]), 4*3^n+1 is for n≥0; and 2(3^n+1), 2²(3^n+1), 2(2*3^n+1) are all the unique ways of factoring those numbers into (non-3) m-irreducibles (for n≥4, n≥4, and n≥1 respectively). And so we get coefficients of k+1, k+1, (k+1)^2, (k+1)*(k+2 choose 2), and (k+1)^2, repsectively. (While 56, 1024, and 112 yield coefficients of (k+1)*(k+3 choose 3), (k+10 choose 10), and k*(k+4 choose 4).)
Or, I mean, those are the coefficients they should yield, if I'm right about how all this works. But they work as an upper bound and I guess that's the important part...
-Harry
[0]There's a good reason for this which I won't explain now but if you understand where this numerical conjecture is coming from at least the ad-hoc reason should be clear.
