Skip to main content
MathOverflow

Return to Question

added 1518 characters in body
Source Link
Neill Clift
Neill Clift
  • 97
  • 5

UPDATE: I was able to find a strategy that seems to make the computation at least possible to perform. Run time to reduce the data will probably still take months. The trick is to identify what you might call primitive convex sets. If we say the data, we are trying to reduce is a union of convex sets $D=\cup_{i=1}^n C_i$. We say a convex set $C_q$ is primitive if a lattice point $x\in C_q$ but $x\notin C_j, j\ne q$. A primitive convex set can't be removed from $D$ without causing the lattice point $x$ being dropped from $D$. It turns out a depth first search to enumerate all possible lattice points $x\in C_q$ with $x$ elements bounded from above is very fast. I search for all exponents less that 128 so essentially a search over all numbers $n<2^{128}$. For each lattice point $x \in C_q$ we try and find another set $C_p$ with $x \in C_p$. It turns out it's fast to determine if a lattice point is contained in another set. If we do not find a $C_p$ then the set is primitive, and we need process it no longer. Otherwise, we stop at the first set we find and record the matching. We use these recorded sets as a cache, and we further enumerate the lattice points in $C_q$. This also turns out to be fast since generally very few and often only one set overlaps with $C_q$. At the end of enumeration, we either know the set is primitive or we have a small list of sets we know can likely be used to eliminate $C_q$. This is obviously multi pass as sets can become primitive as we remove other sets.

1: Goulard, A. Question 393, L'Intermédiaire des Mathématiciens, Vol. 1, 1894

1: Goulard, A. Question 393, L'Intermédiaire des Mathématiciens, Vol. 1, 1894

UPDATE: I was able to find a strategy that seems to make the computation at least possible to perform. Run time to reduce the data will probably still take months. The trick is to identify what you might call primitive convex sets. If we say the data, we are trying to reduce is a union of convex sets $D=\cup_{i=1}^n C_i$. We say a convex set $C_q$ is primitive if a lattice point $x\in C_q$ but $x\notin C_j, j\ne q$. A primitive convex set can't be removed from $D$ without causing the lattice point $x$ being dropped from $D$. It turns out a depth first search to enumerate all possible lattice points $x\in C_q$ with $x$ elements bounded from above is very fast. I search for all exponents less that 128 so essentially a search over all numbers $n<2^{128}$. For each lattice point $x \in C_q$ we try and find another set $C_p$ with $x \in C_p$. It turns out it's fast to determine if a lattice point is contained in another set. If we do not find a $C_p$ then the set is primitive, and we need process it no longer. Otherwise, we stop at the first set we find and record the matching. We use these recorded sets as a cache, and we further enumerate the lattice points in $C_q$. This also turns out to be fast since generally very few and often only one set overlaps with $C_q$. At the end of enumeration, we either know the set is primitive or we have a small list of sets we know can likely be used to eliminate $C_q$. This is obviously multi pass as sets can become primitive as we remove other sets.

1: Goulard, A. Question 393, L'Intermédiaire des Mathématiciens, Vol. 1, 1894

Source Link
Neill Clift
Neill Clift
  • 97
  • 5

Removing convex sets that are unions of other convex sets from a large combinatorial enumeration

An addition chain for $n$ is a sequence of integers $1=a_0<a_1<...<a_r=n$ with $a_i=a_j+a_k,i>j\ge k\ge 0$. We say $r$ is the addition chain length. We define the length of the smallest addition chain for $n$ by $l(n)$.

We have a measure of complexity of addition chains called the small step count. We define $s(n)=l(n)-\lambda(n)$ where $\lambda(n)=\lfloor {log_2(n)}\rfloor$.

If $s(n)=0$ we have $n=2^a$. With $s(n)=1$ we have $n=2^a+2^b,a>b\ge0$. These two cases can be seen with simple limits on $n$ and was first done in 1894 [1]. With $s(n)=2$ things get more complicated. We have 4 cases:

$n=2^a+2^b+2^c,a>b>c\ge0$

$n=2^a+2^b+2^c+2^d,a>b>c>d,1\ge a-b-c+d >= 0$

$n=2^a+2^{a-5}+2^{a-6}+2^{a-7},a\ge7$

$n=2^a+2^{a-3}+2^b+2^{b-1},a>b+3,b\ge1$

Knuth [2] in 1969 has laborious proofs of these cases (stated as 5 cases) in section 4.6.3. He asked though in question 15 to write a computer program to enumerate the $s(n)=3$ case.

Flammenkamp [3] in 1991 wrote the computer program and found 200 cases.

It's clear from the way these cases are constructed that each case has the power of 2 exponents as lattice points in a convex set in $R^{v(n)}$. Here $v(n)$ is the hamming weight of $n$. These are expressed in half-space format. It's clear that some cases could be removed if they are subsets of the unions of other cases. If the union of multiple cases is itself a convex set, we could replace multiple cases with their union. This process can be repeated until each convex set has a unique single vector of exponents as it's member that prevents further reduction. This reduced the $s(n)=3$ from 200 to 150 cases.

This explodes with $s(n)=4$. A new computer program I wrote can enumerate all the cases in under two minutes. It generates 251213 cases. Reducing the number of convex sets by detecting the subsets as mentioned above yielded 40206 cases. This process though is expensive. I detect if two convex sets ($U_1$,$U_2$) have a non-empty intersection. If they do then I compute $U_1\smallsetminus U_2$ as a union of convex sets. This process is repeated in the hopes that the union of convex sets becomes empty and $U_1$ can be discarded.

The case $s(n)=5$ took about 2 weeks to run and has generated 240439903 cases. It's clear I need some different approach to removing these overlaps. No algorithm that's $O(n^2)$ or worse I think has any hope of working. So, the question is are there tricks I can use here to help me reduce the number of cases?

Why do we care? Well, it seems remarkable that $v(n)$ appears to be bounded from above with $s(n)+1\le v(n)\le 2^{s(n)}$ The enumeration clearly shows this for $s(n)\le 5$. To get confidence in the enumeration I check it by making sure the convex sets contain the exponents for all known $n$ with $s(n)\le5$ with $n\le 2^{63}$ (the limits of direct calculations and storage). I can only do this I think if the number of convex sets is much smaller. I expect a vector equivalent of the Frobenius Number might say that if you can test all cases up until some particular vector you have essentially exhausted all cases.

1: Goulard, A. Question 393, L'Intermédiaire des Mathématiciens, Vol. 1, 1894

2: Knuth, Donald E. The art of computer programming, 2: seminumerical algorithms, 1969

3: Flammenkamp, A. Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers 1991