6
$\begingroup$

The circle division problem asks for the number of (bounded) regions obtained after choosing $n$ points in general position on a circle and then cutting along all segments connecting the points (cut along the circle too). The first few answers are $1, 2, 4, 8, 16, \mathbf{31}, \ldots$, and the general formula is $f(n) = {n \choose 4} + {n \choose 2} + 1$. The reason why the sequence starts with binary powers is that we can expand the answer as $\sum_{k = 0}^4 {n - 1 \choose k}$. We also have $f(10) = 256$ since the sum above is a half of a Pascal triangle row.

Denote $S_{n, m} = \sum_{k = 0}^m {n \choose k}$ the prefix sum of $n$-th row of the Pascal triangle. Obviously, $S_{n, 0}$, $S_{n, n}$, $S_{2n + 1, n}$, and $S_{2^t - 1, 1}$ are binary powers. Are there other non-trivial families of $S_{n, m}$ that are always binary powers? Can we characterize all such entries?

Improve this question
$\endgroup$
3
  • $\begingroup$ Of course 2m either has to be 2n or less than n, and I suspect 2m has to be less than n -sqrt(n). Do you have any sense of any other solutions, say when m=2 or m=3? Gerhard "Hasn't Tried Computing This Yet" Paseman, 2017.10.20. $\endgroup$
    – Gerhard Paseman
    Commented Oct 20, 2017 at 23:56
  • $\begingroup$ Is there a natural combinatorial problem that gives $S_{m,n}$ as answer? I was thinking along the line of counting regions again.. $\endgroup$
    – Per Alexandersson
    Commented Oct 21, 2017 at 7:23
  • 1
    $\begingroup$ @PerAlexandersson Define the distance between two binary strings of length $n$ to be the number of positions in which they disagree. Then $S(n,m)$ is the volume/size of a radius $m$ sphere. Essentially this is just “choose $m$ or less out of $n$” but then $2^n/S(n,m)$ is an upper bound on the size of a set of points with minimum distance $2m+1$ so it is intriguing to have that be an integer. $\endgroup$
    – Aaron Meyerowitz
    Commented Oct 21, 2017 at 15:46

1 Answer 1

Reset to default
6
$\begingroup$

I think that is it. But the question turns out to be open.

Your first example is the case $m=4$ of $S_{n,m}=2^m$ for $n \leq m$ while $S_{m+1,m}=2^{m+1}-1$ and also $S_{2m+1,m}=2^m.$ These could be considered to correspond to “perfect” codes with $1$ and $2$ code words.

The celebrated $(23,12,7)-$Golay code would be impossible without the fact that $S_{23,3}=2^{11}.$ The Golay code and the $(2^{n-1},2^n-n-1,3)$-Hamming codes (thanks in part to $S_{2^n-1,1}$) are the only perfect binary codes. I (incorrectly) thought that perhaps this follows from a proof that there are no other non-trivial cases of $S_{n,m}$ a power of $2.$

For a perfect $k$-ary code it would be necessary to have a case of $\sum_0^m\binom{n}{i}(k-1)^i=k^j.$ You were asking about $k=2.$ There is a perfect $(11,6,5)$ $3$-ary code which would not be possible were it not the case that $\binom{11}0+2\binom{11}1+4\binom{11}2=3^5.$

There are no other perfect linear $k$-ary codes. I'm not sure if the proof stems from having no other coincidences as above, at least for $k$ a prime power.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ There's also $S_{90,2} = 2^{12}$, though it's known that there's no perfect binary $[90,78,5]$ code. The theorem of Tietäväinen and van Lint does not require a complete solution of $S_{n,m} = 2^k$ (and the corresponding equation for other prime-power values of the alphabet size $k$); as far as I know it is still an open question whether there are any other cases where $S_{n,m}$ is a power of two (the $m=2$ case is equivalent to the celebrated Ramanujan-Nagell theorem). $\endgroup$
    – Noam D. Elkies
    Commented Oct 21, 2017 at 3:30

You must log in to answer this question.

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