Advances in the minimum overlap problem
type: Item
instance of: scholarly article
title: Advances in the minimum overlap problem
zbMATH Open document ID: 0852.11009
author: Jan Kristian Haugland
published in: Journal of Number Theory
publication date: 1996-07-09T00:00:00Z
review text: Given any positive integer \(n\), consider partitions of the set \(\{1, 2, 3, \dots, 2n\}\) into two disjoint classes \(\{a_i\}\) and \(\{b_j\}\) with \(n\) elements in each class. Let \(M_k\) denote the number of solutions of \(a_i- b_j= k\). Let \(M(n)= \min \max_k M_k\) where the minimum is taken over all partitions. To estimate \(M(n)\) is the minimum overlap problem introduced by \textit{P. Erdös} [Riveon Lematematika 9, 45-48 (1955); Colloque Théorie des Nombres, Bruxelles 1955, 127-137 (1956; Zbl 0073.03102)]. It is known that \(0.3564\leq \lim M(n)/ n\leq 0.4\). As to the upper bound, see \textit{T. S. Motzkin}, \textit{K. E. Ralston} and \textit{J. L. Selfridge} [Bull. Am. Math. Soc. 62, 558 (1956)]. In the paper under review the author improves the upper bound to 0.3857. A crucial conjecture of the author is proved by P. Swinnerton-Dyer and his proof is reproduced in the paper. This result allows the further improvement to 0.3821.
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 05A18
zbMATH DE Number: 883835
zbMATH Keywords: partitions of sets
zbMATH Keywords: upper bound
zbMATH Keywords: minimum overlap problem
reviewed by: Mihály Szalay
MaRDI profile type: Publication
full work available at URL: jnth.1996.0064
OpenAlex ID: W2072556229
DOI: 10.1006/JNTH.1996.0064
description: scientific article; zbMATH DE number 883835