4
$\begingroup$

This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$.

The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\pm3\pm5…\pm n=0$" give the asymptotics as $n\to\infty$, respectively
$$\sqrt{\frac6 \pi}\frac{2^n}{n^{3/2}}\quad \text{ and }\quad 2\sqrt{\frac6\pi}\frac{2^{n/2}}{n^{3/2}} $$ (the first one only applies for $n \equiv 0$ or $3 \pmod 4$, the second one only for $n \equiv 3 \pmod 4$, as otherwise there are no solutions).

Note that in the second one, I have replaced $4n-1$ by $n$, with the outcome that both asymptotic formulae become very similar. This naturally raises the question for the asymptotics of the number of solutions in other arithmetic progressions:

Fix coprime $d>r$. For $m\in\mathbb N$, consider the set $\{d-r,2d-r,\dots, md-r \} $ and ask about the number $f_{d,r}(m)$ of partitions into two sets with the same sum, more precisely its asymptotics for $m\to\infty$, as formulae for the exact number seem out of reach even for the two "simplest" cases corresponding to $f_{1,0}$ and $f_{2,1}$ above.

Of course we only consider those $n$ where solutions are possible, i.e. where $m(m+1)d-2mr\equiv0\pmod4$.

We may express the asymptotics also in terms of $n:=md-r$ instead of $m$. My conjecture from numerical calculations for small $d$ is that generally (with "$\sim$" meaning proportional) $$f_{d,r}(m)\sim\dfrac{2^{n/d}}{n^{3/2}} \sim\dfrac{2^{m}}{n^{3/2}}\sim\dfrac{2^{m}}{(md)^{3/2}}\sim\dfrac{2^{m}}{m^{3/2}} .$$ If true, this would mean the quite intriguing result that the asymptotic behavior is essentially the same for all arithmetic progressions. This seems not at all obvious!

Any insights about the asymptotics? And what about the constants?

Generally for $d\ge3$, they do not seem to be just "easy rational" multiples of $\sqrt{\dfrac6 \pi}$, and unlike the magnitude, they also depend on $r$. Numerically for $d\ge4$, it looks like there are always two alternating orbits for these constants, with the same limit $\liminf=\limsup$ (meaning kind of like $C+\frac{(-1)^n}n$).

EDIT Under the very realistic assumption that the Central Limit theorem applies, @AnthonyQuas has got much better numerical approximations for the constants and suggested in a comment the following conjecture, which seems indeed to hold: $$\boxed{f_{d,r}(m)\sim\sqrt{\frac6 \pi}\frac1d\dfrac{2^{m}}{m^{3/2}} }.$$ Note that by introducing $2^m$ instead of $2^n$, we get in fact rid of the $r$.

N.B. The restriction $d>r$ seems in fact irrelevant. Even if the sets contain negative numbers, the asymptotic behavior seems to remain exactly the same. Note that it is not possible to just increase each set member by the same amount, as the two subsets with equal sum may have different sizes. (But asymptotically that doesn't seem to make a difference, not more than the occurrence of a few negative numbers.)

$\endgroup$
  • $\begingroup$ Is there a chance that the number of solutions with equal number of pluses and minuses prevails in the asymptotic? That would eliminate $r$ from the main term, and essentially make it depend only on $n$ and $m\approx n/d$. $\endgroup$ – Max Alekseyev Oct 2 '17 at 4:30
  • 1
    $\begingroup$ I haven’t tried calculating yet, but can you just get the constants out of the central limit theorem? I have in mind adding or subtracting each term with equal probability, and trying to estimate the probability that you obtain 0. The distribution of this sum should be very close to a normal random variable, probably with very nice “smooth” densities on Z. $\endgroup$ – Anthony Quas Oct 2 '17 at 5:27
  • $\begingroup$ @MaxAlekseyev Intuitively, I would expect the number of pluses and minuses for fixed d,r,m to behave itself like a gaussian curve (with fairly small variance that should tend to 0 for $m\to\infty$ with d,r fixed). That might be a different question. $\endgroup$ – Wolfgang Oct 2 '17 at 9:00
  • $\begingroup$ @AnthonyQuas Maybe. I was already reminded of the central limit theorem because of the $1/\sqrt{\pi}$ lurking out, but I wonder if it is applicable given that the two subsets must have exactly the same sum. For "near-same" sum it would seem more plausible. Anyway, probability theory is not my domain. Would you think it's worth adding the probability tag? $\endgroup$ – Wolfgang Oct 2 '17 at 9:21
  • $\begingroup$ So I did the calculations with the CLT. This is still heuristic at this point, but I think the correct answer should be $\sqrt{d}\times \sqrt{6/\pi}2^m/n^{3/2}$. Are there any examples that suggest that this isn't right? By the way, it's probably more natural to express everything in terms of $m$ and $d$: $\sqrt{6/\pi}2^m/(m^{3/2}d)$. $\endgroup$ – Anthony Quas Oct 3 '17 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.