On the maximum number of points at least one unit away from each other in the unit n -cube
- PDF / 129,399 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 91 Downloads / 165 Views
ON THE MAXIMUM NUMBER OF POINTS AT LEAST ONE UNIT AWAY FROM EACH OTHER IN THE UNIT n-CUBE ´lint1 and Vojtech Ba ´lint jr.2 Vojtech Ba [Communicated by Imre B´ ar´ any] 1
ˇ Univerzitn´ a 1, 01026 Zilina, Slovakia E-mail: [email protected] 2 ˇ ˇ N´ am. Ludov´ ıta Fullu 15, 01008 Zilina, Slovakia E-mail: [email protected] (Received March 3, 2008; Accepted March 18, 2008)
Abstract We present a very short survey of known results and many new estimates and results on the maximum number of points that can be chosen in the n-dimensional unit cube so that every distance between them is at least 1.
The n-dimensional unit cube [0, 1]n will be called here the n-cube, for short. The following problem was stated in [10] and later repeated in [6]. Let f (n) denote the maximum number of points that can be chosen in the n-cube so that every distance between them is at least 1. Obviously, f (n) = 2n for n ≤ 3. Many have shown that log f (n) ∼ 21 n(log n). Determine f (n), at least for reasonably small values of n, and sharpen the asymptotic estimate. Let us recall some of the previously known and published relevant results. Theorem 1. ([2]) The only configuration realizing f (3) = 8 is the set of vertices of the 3-cube. Theorem 2. ([1]) We have f (4) = 17, and the only configuration realizing f (4) is the set consisting of the 16 vertices of the 4-cube and the cube’s center. Let F (n) denote any set of points realizing the value of f (n) for the n-cube. We will refer to such a set as an extreme set for the n-cube. Mathematics subject classification numbers: 52C17, 05B99. Key words and phrases: packing, point, cube. 1,2 Research was supported by Slovak national grant VEGA 1/3839/06. 0031-5303/2008/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
84
´ ´ V. BALINT and V. BALINT JR.
Theorem 3. ([1]) If F (5) contains all vertices of the 5-cube, then f (5) = 34. Theorem 4. ([1]) If F (6) contains all vertices of the 6-cube, then f (6) = 76. Theorem 5. ([4]) f (5) ≤ 44. In [1] we mention the following conjectures: f (5) = 34, f (6) = 76, f (7) = 152, and f (8) = 353 (see also [6, p. 34]). We still believe that the first two of our conjectures are true, but the last two of them turned out to be false. Already in [2] we constructed more numerous sets that give better lower bounds: f (7) ≥ 184 and f (8) ≥ 481. Let us also remark that it is easy to construct sets of points to show that f (9) ≥ 994, f (10) ≥ 2452, f (11) ≥ 5464, and f (12) ≥ 14705 (see also [5, p. 71]). While any construction of a suitable set of points gives a lower bound for f (n), getting a good upper bound is usually much more difficult. √ √ √ Let k = n + 1 in case n is an integer, otherwise let k = ⌈ n ⌉. Then the n-cube can be dissected into k n congruent smaller cubes, each of diameter √ n/k < 1, by hyperplanes perpendicular to the coordinate axes. Obviously, the pigeon-hole principle implies f (n) ≤ k n which gives the following, trivial upper bounds: f (5) ≤ 35 = 243, f (6) ≤ 36 = 729, f (7) ≤ 37 = 2187, f (8) ≤ 38 =
Data Loading...
