Improved algorithms for left factorial residues

The paper “Improved algorithms for left factorial residues” written by Vladica Andrejic, Alin Bostan, and me will appear in Information Processing Letters.

“We present improved algorithms for computing the left factorial residues !p = 0! + 1! + \dots + (p-1)! \mod p. We use these algorithms for the calculation of the residues !p \mod p, for all primes p up to 2^{40}. Our results confirm that Kurepa’s left factorial conjecture is still an open problem, as they show that there are no odd primes p < 2^{40} such that p divides !p. Additionally, we confirm that there are no socialist primes p with 5 < p < 2^{40}."

The implementation of the algorithms presented in the paper is available at

[PDF] [arXiv]

New lower bounds for some small Ramsey numbers

The new revision of the dynamic survey Small Ramsey Numbers has recently been published [2]. I’m happy to see that many of the lower bounds G. Exoo and I obtained in [1] are included. I’m going to use this post to maintain the updates on the bounds that weren’t listed in the survey.

Ramsey Number Old Bound [2] New Bound
R(7,8) 217 219
R(6,11) 256 262
R(4,15) 155 158
R(4,16) 166 170
R(12,12) 1639 1640

All constructions are available here.

[1] G. Exoo and M. Tatarevic, New Lower Bounds for 28 Classical Ramsey Numbers, The Electronic Journal of Combinatorics, 22 (3), #P11, 2015. [PDF]
[2] S. P. Radziszowski, Small Ramsey Numbers, The Electronic Journal of Combinatorics, #DS1, 2017. [PDF]

On the Ramsey Number R(12,12)

Improving the lower bounds for some small diagonal Ramsey numbers R(k, k) seems to be surprisingly difficult. Although a significant effort has been made, most of the lower bounds for 6 \leq k \leq 16 did not change over the last few decades. These lower bounds are either obtained from Paley colorings (k=6,8,10) or by the construction discovered independently by Mathon [1] and Shearer [2] (k=7,9,11,13,14,15,16). The Ramsey number R(12, 12) is an interesting exception, with the lower bound derived consequently as some more general inequalities were improved. The last such effort is described in [3], where Xu, Shao and Radziszowski proved the following general inequality:

R(k, s + 1) \geq R(k, s) + 2k - 2\  for  k \geq 5. \ \ \ \ \ (1)

They established the lower bound for R(12,12) by applying this inequality two times. First, we have R(11, 12) \geq R(11, 11) + 2 \cdot 11 - 2 \geq 1617, and then R(12, 12) \geq R(12, 11) + 2 \cdot 12 - 2 \geq 1639.

We can show that this bound can be slightly improved by analyzing the colorings of lower order. In particular, I examined the construction used to prove the inequality (1) for the case where (k, k + 1)-coloring is derived from the best known (k, k)-coloring.

Let me first note that I did not find a way to improve the (k, k + 1)-coloring obtained by (1) by simply adding a new vertex and recoloring the edges. But, this process produced an interesting side effect. After one vertex is added and recoloring of the edges is performed, the best coloring I got contained one K_{k} in the first color, and no K_{k+1} in the second color. I was able to replicate this construction for 7 \leq k \leq 11. If we use a complement of the graph obtained by this new construction, and then apply the construction used to prove (1), it is possible to produce a coloring with one K_{k+1} in the first color and k \ K_{k+1} in the second color. These remaining K_{k+1} can be eliminated by running a local improvement procedure. This result yields the next theorem.

Theorem. R(12,12) \geq 1640.

Proof. The proof is given by the existence of the (12,12)-coloring of K_{1639} that can be downloaded here. \square

Note that the computation time required to verify this coloring can be significantly reduced by exploiting the fact that this graph already contains a (11,11)-coloring on 1596 vertices. Additionally, to confirm the validity of this coloring, I verified the result using the several different implementations of the exact algorithms for the maximum clique problem, available online.

The approach described above implies that there is a good chance that the more general R(k+1,s+1) \geq R(k,s) + 2k + 2s - 1 holds for k \geq 5. Although this inequality is weak, I did not find a way to prove it. Feel free to contact me if you are interested in working on this problem.

[1] R. Mathon, Lower Bounds for Ramsey Numbers and Association Schemes, Journal of Combinatorial Theory, Series B, 42: 122–127, 1987.
[2] J. B. Shearer, Lower Bounds for Small Diagonal Ramsey Numbers, Journal of Combinatorial Theory, Series A, 42: 302–304, 1986.
[3] X. Xiaodong, Z. Shao and S.P. Radziszowski, More Constructive Lower Bounds on Classical Ramsey Numbers, SIAM Journal on Discrete Mathematics, 25: 394–400, 2011.

On distinct residues of factorials

The paper “On distinct residues of factorials” written by Vladica Andrejic and me will appear in Publications de l’Institut Mathématique.

“We investigate the existence of primes p > 5 for which the residues of
2!, 3!, ..., (p-1)! modulo p are all distinct. We describe the connection
between this problem and Kurepa’s left factorial function, and report that there are no such primes less than 10^{11}.”

[PDF] [arXiv]

New Lower Bounds for 28 Classical Ramsey Numbers

Recently, Geoffrey Exoo and I performed an extensive search and improved the lower bounds for 28 classical Ramsey numbers. We also introduced several new search techniques. Our paper, with summarized results and methods, is published in the Electronic Journal of Combinatorics.

“We establish new lower bounds for 28 classical two and three color Ramsey numbers, and describe the heuristic search procedures we used. Several of the new three color bounds are derived from the two color constructions; specifically, we were able to use (5,k)-colorings to obtain new (3,3,k)-colorings, and (7,k)-colorings to obtain new (3,4,k)-colorings. Some of the other new constructions in the paper are derived from two well-known colorings: the Paley coloring of K_{101} and the cubic coloring of K_{127}.”

[PDF] [E-JC] [arXiv] [MR] [DATA]

On Limits of Dense Packing of Equal Spheres in a Cube

My paper “On Limits of Dense Packing of Equal Spheres in a Cube” is published in the Electronic Journal of Combinatorics.

“We examine packing of n congruent spheres in a cube when n is
close but less than the number of spheres in a regular cubic close-packed (ccp) arrangement of  \lceil p^3/2\rceil spheres. For this family of packings, the previous best-known arrangements were usually derived from a ccp by omission of a certain number of spheres without changing the initial structure. In this paper, we show that better arrangements exist for all n \leq \lceil p^3/2\rceil - 2. We introduce an optimization method to reveal improvements of these packings, and present many new improvements for n \leq 4629.”

[PDF][E-JC][arXiv] [MR]

Searching for a counterexample to Kurepa’s Conjecture

The paper Vladica Andrejic and I wrote regarding the Kurepa’s left factorial conjecture will appear in Mathematics of Computation.

“Kurepa’s conjecture states that there is no odd prime p that
divides !p=0!+1!+...+(p-1)!. We search for a counterexample to
this conjecture for all p<2^{34}. We introduce new optimization
techniques and perform the computation using graphics processing
units. Additionally, we consider the generalized Kurepa's left
factorial given by !^{k}n=(0!)^k +(1!)^k +...+((n-1)!)^{k}, and show
that for all integers 1<k<100 there exists an odd prime p such
that p|!^{k}p.”

[PDF] [arXiv] [MCOM] [MR]

Construction of Ramsey (4,6)-Coloring

In 2012, Geoffrey Exoo improved the lower bound of the Ramsey number R(4,6) by discovering 37 new colorings of the complete graph on 35 vertices [1]. This result was unexpected while similar bounds weren’t improved for years. For example, there is a strong evidence that R(5,5) is most likely 43 [3], or similarly that further improvements of R(3,10) aren’t expected [2].

Recently, I found a slightly different method than one described in Exoo’s paper.

Construction requires two steps:

  1. The initial adjacency matrix A is produced using eleven 7 \times 7 circulant matrices given below. By circ(a_0, a_1, \ldots, a_n) we denote circulant matrix with the first row (a_0, a_1, \ldots, a_n).
    Described coloring has no monochromatic copies of K_4 in the first color, and there are only 7 monochromatic copies of K_6 in the second color.

    B = circ(0,1,1,0,0,1,1)
    C = circ(0,1,1,0,1,1,0)
    D = circ(0,1,1,1,1,1,0)
    E = circ(0,1,0,1,1,1,1)
    F = circ(0,0,0,0,1,1,0)
    G = circ(0,1,0,1,1,0,1)
    H = circ(0,1,1,0,0,0,0)
    I = circ(1,0,0,1,1,0,1)
    J = circ(0,0,1,1,1,1,0)
    K = circ(1,0,0,1,1,1,1)
    L = circ(0,1,1,0,1,0,1)

    A=\left[\begin{array}{ccccc}  B & C & D & E & F\\  C^{t} & G & G & H & I\\  D^{t} & G^{t} & J & K & L\\  E^{t} & H^{t} & K^{t} & B & B\\  F^{t} & I^{t} & L^{t} & B^{t} & G  \end{array}\right]

  2. Bad subgraphs are eliminated using simulated annealing. The adjacency matrix is given below.


[1] G. Exoo, On the Ramsey Number R (4, 6), Electronic Journal of Combinatorics, #P66, 19(1) (2012)
[2] G. Exoo, On Some Small Classical Ramsey Numbers, Electronic Journal of Combinatorics, #P68, 20(1) (2013)
[3] B.D. McKay and S.P. Radziszowski, Subgraph Counting Identities and Ramsey Numbers, Journal of Combinatorial Theory, Series B, 69 (1997) 193-209.

Improved packing of 29 unit spheres in a cube

For a long time, it was conjectured that an optimal packing of 29 unit spheres in a cube is derived from the best-known packing of 32 spheres by the omission of 3 spheres. In this case, all spheres are arranged in a cubic close-packed structure. Thus, the minimum side length of a cube is exactly 2 + 3\sqrt{2}.
It was hard to imagine that there is a way to improve this configuration. By performing a search, you can easily obtain a packing such that the cube side length will match 60+ digits of 2 + 3\sqrt{2}. Even if you repeat the search hundreds of times, the results will match again.

To obtain a better packing, you need slightly different approach. I will try to explain these constructions in one of the next posts. The improvement I found is significant considering small n and fact that this packing wasn’t improved for a long time (Goldberg a found solution for n=32 in 1971).

Cube side length of an improved solution is:
6.24264068710234570089614585735 (which is approximately 2 + 3\sqrt{2} - 1.69 \cdot 10^{-11})

Continue reading “Improved packing of 29 unit spheres in a cube”

Packing equal spheres in a cube. Improvements for n = 29, 47 and 59

Finite sphere packing, although similar to circle packing, is much harder problem (for the same n) and often requires different optimization techniques. Packing equal circles in a square is probably one of the most examined packing problems. Optimality is proved for n<31 and n=36, and very few other packings for n<100 can be further improved. If such configurations exist, difference between square side length of improved solution and the current record is probably less than 10^{-20}.

On other side, significant improvements in finite sphere packing are mostly done in the last few years (all available at Packomania). Most of the packings for n<50 are near-optimal. I was able to reproduce most of the results easily, but in the same time, had huge problems with resolving some configurations (like for n=28, 42, 49).

Search was focused on small n, and improvements were found for n=29, 47, 59.

Continue reading “Packing equal spheres in a cube. Improvements for n = 29, 47 and 59”