First Written: Jan. 15, 2018

Appeared in Mathematics Magazine v. 93 (2020), issue 1, 54-61 [in a slightly "edited" version, but we prefer the original],

Bob Hough recently disproved a long-standing conjecture of Paul Erdos regarding covering systems. Inspired by his seminal paper, we describe analogs of covering systems to Boolean functions, and more generally, the problem of covering discrete hyper-boxes by non-parallel lower dimensional hyper-subboxes. We point out that very often primes are red herrings. This is definitely the case for covering system, and who knows, perhaps also for the Riemann Hypothesis.

Added Feb. 9, 2019: Read this interesting follow-up article by Manuel Kauers, Martina Seidl, and Doron Zeilberger.

Added Feb. 16, 2020: Read this cute blog-post by Richard Lipton.

Added Aug. 24, 2020: Rob Pratt met one of our challenges, namely for n=10 and k=7. See his amazing DNF

Maple packages

• dt.txt, a Maple package to discover distinct DNF tautologies, as well as generalizations to multi-valued logic.

Sample Input and Output for dt.txt

• If you want to see optimal distinct DNF tautolgies all of the same size, with the size as large as possible (whenever possible)

  the input file generates the output file.

• If you want to see optimal distinct DNF tautolgies all with the smallest size as large as possible, (whenever possible)

  the input file generates the output file.

Doron Zeilberger's Home Page

Anthony Zaleski's Home Page