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 https://github.com/milostatarevic/left-factorial

[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:

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]$
Bad subgraphs are eliminated using simulated annealing. The adjacency matrix is given below.

01100110111110011111000011110000110

10110000011011001111110101110000011

11011001001101100111111010111000001

01101101100110110011111100011100000

00110110110011111001111110000110000

10011011011001111100101111010011000

10001101101100111110010111100001100

00110110101111010110101100001001111

10011011010110101011000110001100111

11001100101111010101100011001110011

11100111010101101010100001101111001

10110011111010110101000000111101100

11011001110101011010110000010111110

01101101011010101101011000000011111

00111110101101001001110011110110101

10011111010110000100111001111011010

11001110101011100110111100110101101

11100111010101011011011110011010110

11110011101010001100111111000101011

11111000110101100100001111101010101

01111101011010111010000111111101010

01111010000011111110001000110110011

00111101000001011111010110011111001

01011111100000001111101011001101100

10101110110000100111101101100110110

11000110011000110011100110110011011

11100010001100111001110011011001101

11110100000110111100111001101100110

00110001111100010101101100110111101

00011000111110101010111110011010110

00001100011011110101011011001101011

00000111001111011010101101101010101

10000011100111101101000110111101011

11000001110011010110110011010110101

01100001111001101011011001101011110

[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$ ).