Talk:Kissing number

Contradiction of Leech lattice

"In 24 dimensions, the kissing packing places the spheres at the points of the Leech lattice and there is no space at all left over," but from Leech lattice, "It seems to be expected that this configuration also gives the densest packing of balls in 24-dimensional space, but this is still open." These don't seem to agree. Correct me if I'm wrong but this page claims that the Leech latice is the best packing of spheres in 24 dimensions but the Leech latice page says that we aren't sure yet. Which is correct? I'd wager the Leech latice page is but I've never heard of this problem before so I'm not going to change it. Can a mathematician change one of these two pages please? -- Rory ☺ 23:01, May 31, 2004 (UTC)

( It sucks that this has been around for so long without being fixed. There is only an upper bound proven how much better an irregular packing could be in the 24-d case, so the article was clearly wrong. You should have removed the suspect uncited claim as thats always the safe thing to do. --71.191.135.140 (talk) 04:44, 20 September 2008 (UTC)[reply]

No, the two statements aren't in contradiction with each other. The Leech lattice (lambda-24) has been proven to have the highest possible _kissing number_ among all arrangements, whereas it has not been proven to have the highest _density_ among all arrangements. There is no evidence to suggest that there is a denser packing of 24-dimensional spheres, and, if there is such a packing, it can only be microscopically denser (by a factor of about 10^-30). --Calcyman (talk) 15:34, 11 April 2010 (UTC)[reply]

Ref

Could anybody give a ref to the statements in dim 8 and 24? Tosha 15:37, 8 Jul 2004 (UTC)

http://www.research.att.com/~njas/doc/interview.html says this is by Sloane/Odlyzko and V. Levenshtein, independently. Charles Matthews

It's 24! It's 24!

Just a hunch. It rests better with the factors that be. :) --mwazzap 07:50, 29 October 2005 (UTC)[reply]

It is 24

It was recently proven by Oleg Musin that in fact the kissing number in four dimensions is 24. See http://arxiv.org/pdf/math.MG/0309430 for a preprint of the article, or http://www.ams.org/notices/200408/fea-pfender.pdf to learn more about the topic.

I think the kissing number K(n) of an n-D Euclidean space can be found from K(n–1) by constructing n-D equilateral "triangles"; that is,

  K(n)=K(n-1)+(number of admissible new vertices).

Admissible vertices are those at least one diameter apart. The approach gives K(1)=2, K(2)=6, K(3)=12, K(4)=24, but K(5)=48. The last number is larger than the reported bound. Is K(5)=48 correct? The approach also gives an upper bound as K(n)/2ⁿ < or =3/2 for large n. 209.167.89.139 16:22, 15 September 2006 (UTC)[reply]

math.MG/0608426

This preprint claims better upper bounds for 5, 6, 7, 9, and 10. Melchoir 05:32, 18 August 2006 (UTC)[reply]

One dimension ?

You can't draw circles in one dimension, right ?--George (talk) 11:03, 11 March 2008 (UTC)[reply]

You can have a mathematical equivalent of a circle on 1-dimensional line - it is just the two points that are the same distance either side of some central point. Algebraically, a circle on a 1-dimensional line with centre x and radius y is the two points x-y and x+y, which bound a (closed) 1-dimensional disk which is just the interval or line segment [x-y, x+y]. This is what the very first diagram in the "Known kissing numbers" section is trying to illustrate. Gandalf61 (talk) 12:06, 11 March 2008 (UTC)[reply]

Right, thanks --George (talk) 21:08, 11 March 2008 (UTC)[reply]

n = 1 to 9

MathWorld and A001116 claim that kissing numbers are known for $n=1$ to $9$ . VladimirReshetnikov (talk) 20:57, 19 December 2008 (UTC)[reply]

The values are known for regular arrangements of spheres in 1 to 9 dimensions, where the centres of the spheres occupy points on a lattice. Proving that the maximum kissing number for lattice arrangements is indeed the maximum kissing number for any arrangement of spheres is a much more difficult problem.

The maximum kissing number for any arrangement of spheres is only known in 1,2 ,3 4, 8 and 24 dimensions. In each case the best arrangement happens to be a lattice arrangement. However, we know that in 9 dimensions the best arrangement is not a lattice arrangement - the maximum lattice kissing number in 9 dimensions is 272, but a non-lattice arrangement is known with a kissing number of 306. Same applies for dimensions 10 to 14 - a non-lattice arrangement has been found with a higher kissing number than the best lattice arrangement. In 5, 6 and 7 dimensions no one has found a non-lattice arrangement that has a higher kissing number than the best lattice arrangement - but neither has it been proved that one does not exist.

I agree that the article could do a better job of explaining the difference between lattice and non-lattice arrangements, and could show the known results for lattice arrangements. Gandalf61 (talk) 12:36, 20 December 2008 (UTC)[reply]

Can anyone please reconcile or unify the table in this article and that in Wolfram? The two tables give different kissing numbers for 5≤n≤7. If K(n+1)=K(n)+[2×K(n)]/m, no integer m can be found to satisfy K(5) to K(7) in either table. Can we conject that the reported K(n) might be incorrect? Also, why has there been no answer to the question raised about a contradiction to Leech's Lattice for n=24? Thanks. Zymogen (talk) 00:32, 23 December 2008 (UTC)[reply]

Our table gives known values or bounds for the kissing number across all arrangements, both lattice and non-lattice. Wolfram omits the non-lattice values (column NL in their table) for dimensions 5, 6 and 7 because the highest known kissing number in those dimensions is for a lattice arrangement (column L in Wolfram). However, as I explained above, it has not been proved that this is the highest kissing number across all arrangements, so our table gives the known bounds for those dimensions - the lower bound is, of course, the highest known kissing number, and the upper bound will have been derived from geometric/volumetric arguments. The distinction between known and proven maximum kissing numbers seems to cause some confusion, so I will expand our article at some point over the next few days to give a better explanation. Gandalf61 (talk) 09:02, 23 December 2008 (UTC)[reply]

I appreciate your clarifications very much. If you do not mind, I would like to ask three more questions: (a) Is a triangular packing a lattice or a non-lattice pattern? (b) Is it true that all K(n) ought to be even, regardless of the pattern? (c) Rory in the first post questioned Leech's K(24) being the largest KN for that dimension. Is he correct? I think he is. Zymogen (talk) 18:53, 23 December 2008 (UTC)[reply]

I can answer these questions. (a) If by "triangular packing", you mean a packing where the centers of spheres lie on the vertices of a hexagonal lattice, then by definition it is a lattice packing. (b) The answer to this question is not known. (c) From my reading of Rory's post, I think he's actually questioning whether the Leech lattice is known to be the densest packing -- in fact it is known to be the configuration which gives the highest kissing number, which is an entirely different question, see these pages from the book by Sloane and Conway[1]. Akriasas (talk) 22:23, 24 December 2008 (UTC)[reply]

Thank you very much for your answers. (a) By "triangular packing", I mean the centers of n-D hyper-spheres lie on the vertices of n-D hyper-triangles. (b) For the aforementioned packing pattern, I think it ought to be possible to use an n-D hyper-triangle as a base to build an (n+1)-D hyper-triangle. Each base will introduce two out-of-plane apexes, one on the positive x(n+1) axis and another one on the negative x(n+1) axis. Since K(1)=2, all K(n) thereafter ought to be even. Anyway, that is just a thought. (c) Do you think a K(24) much larger than that given by Leech Lattice could exist? Zymogen (talk) 02:49, 25 December 2008 (UTC)[reply]

pi's revenge

Just for fun, I did a linear regression on the means of the logarithms of the known bounds, and got $e^{0.451309n+1.33904}$ , which is fascinatingly close to $3.815\left({\frac {\pi }{2}}\right)^{n}$ . Does anyone know whether this possibility for the base of the (presumed) exponential growth has been investigated, and perhaps ruled out? --Tardis (talk) 23:30, 21 May 2009 (UTC)[reply]

This is interesting. How accurate are the coefficients in that regression? Is it possible that the base isn't pi/2 but, say, the Golden ratio? The two are only off by only 3%, and phi^n would make this problem a cousin of the Fibonacci sequence. Owen× ☎ 01:18, 22 May 2009 (UTC)[reply]

e^{0.451309}=0.499863\pi

(to that precision, given the precision to which I gave my coefficient), which is 0.027% low. Obviously the uncertainty in my fit parameters is much larger, since I have only a few data points, most of them are estimates (the geometric means), and the inputs are integers that cannot lie exactly on any exponential. But it's (whether by happenstance or not) a lot closer than 3% to

\pi /2

. --Tardis (talk) 19:38, 22 May 2009 (UTC)[reply]

You are right, it is closer to pi/2 up to n=24. But do we have reason to believe it rises exponentially at all? From n=4 to n=8, it grows proportionally to 1.7782^n, while from n=8 to n=24, it's 1.5208^n. If you go all the way to n=48 (52416000), it's 1.2621^n, which is nowhere near pi/2. Perhaps asymptotically it isn't exponential at all. Owen× ☎ 01:16, 23 May 2009 (UTC)[reply]

We do know that it's exponential — there are known exponential upper and lower bounds. It's just that the base of the exponent in the upper bounds is different from the one in the lower bounds, so we don't know what the correct exponential function is. π/2 seems like a very interesting guess for the correct base of the exponential. —David Eppstein (talk) 01:29, 23 May 2009 (UTC)[reply]

It may be easy to prove an exponential as an upper bound. I don't have any values beyond n=128, but for any range with n>24, pi/2 seems like a gross overestimate for the base, and the value for the base keeps shrinking as we move higher. If you chart the function on a log scale, you'll see it clearly growing slower than exponentially, although of course that's far from an actual proof. Owen× ☎ 01:36, 23 May 2009 (UTC)[reply]

It is very easy to prove a 2^n + 1 upper bound. Suppose one has a collection of k unit spheres, all touching a central unit sphere centered at the origin. Then each of the given spheres has at least half of its volume inside of a sphere of radius 2 centered at the origin. Therefore, the sum of the volumes of the k unit spheres is at most twice the volume of the radius-2 sphere. But the volume of a sphere scales as the nth power of its radius, so the volume of the radius-2 sphere is 2ⁿ times that of the unit sphere. Therefore, k must be at most 2^n + 1, or else all the little half-spheres inside the radius-2 sphere would be bigger than the radius-2 sphere itself. —David Eppstein (talk) 02:04, 23 May 2009 (UTC) This argument isn't right (it would give √5ⁿ not 2ⁿ) but anyway Bezdek cites a tighter known bound. —David Eppstein (talk) 03:26, 23 May 2009 (UTC)[reply]

As I've said, an exponential upper bound is obvious. But the actual kissing number seems to rise much slower than exponential, as per my comment above. Owen× ☎ 03:08, 23 May 2009 (UTC)[reply]

As I said above (but maybe you didn't notice), exponential lower bounds are also known. Specifically, according to Bezdek, there is a lower bound of approximately 1.1547ⁿ due to Wyner, A. D. (1965), "Capabilities of bounded discrepancy decoding", Bell Systems Tech. J., 54: 1061–1122.

I just looked again at the Bezdek survey I cited above. It mentions a known upper bound of approximately 1.320ⁿ, less than π/2. So I guess this guess at the base of the exponential cannot be π/2. Oh well. The reference given by Bezdek is Kabatiansky, G. A.; Levenshtein, V. I. (1978), "Bounds for packings on a sphere and in space", Problemy Peredachi Informatsii, 14: 3–25.

Sorry, I missed your comment about an exponential lower bound. I wasn't aware of Bezdek's work--thanks for bringing it to my attention! I guess the 1.2621^n I mentioned wasn't that far off... Owen× ☎ 12:48, 23 May 2009 (UTC)[reply]

Musin?

The link to Oleg Musin is to an article about a football player. Same person? There's no mention of a mathematical career in the article.

Yes, link definitely points to wrong Oleg Musin, so I have removed it. Gandalf61 (talk) 08:41, 25 September 2009 (UTC)[reply]

Musin's subtle trick

The "Known kissing numbers" section currently has the text Oleg Musin proved the kissing number for n = 4 to be 24, using a subtle trick, followed by a reference. This doesn't seem quite right. If we're going to tell our readers it was a subtle trick, shouldn't we also tell them at least something about what the trick was?

It would be sifferent if subtle trick was in quotes, but that phrase doesn't appear in the JAMS (Pfender & Ziegler) article. They seem to be actually discussing Musin's ideas from a preprint, unrefereed form of the paper, and include the opinion "The bad news about Musin’s approach is that it forces him to compute, at least approximately...", so it's not clear exactly how clever the whole thing is, since it seems to rely on approximations (and I realize that a lot of higher math proofs latterly use that approach). But the subtle trick bit of the article looks like a paraphrase of two people's opinion, which may or may not be confirmed over time and in any case is not properly explained within the text body.

So what I'm suggesting is: add a rudimentary explanation of what the trick actually was; quotationize the phrase and make it true to the reference, so any of "clever modification", "beautiful idea", "clever way" would work fine; or just drop the subtle trick synthesis. I'm not even close to competent at interpreting the actual maths, so I suppose my own response would be to pull the phrase. I'll leave it in the hands of editors better able to explicate this stuff. Regards! Franamax (talk) 07:40, 6 October 2009 (UTC)[reply]

Questionable bounds

Based on my observation, I suspect the upper bound for 22 is no greater than 75600...--Billymac00 (talk) 23:38, 6 November 2009 (UTC)[reply]

Maximum number?

The intro definition seems to imply the kissing number is the maximum for a given dimension, while other contexts talk about maximum known kissing number [2]. Is it wrong to say a kissing number of a given lattice/packing is X, even if X<maximum? 75.146.178.58 (talk) 21:30, 10 July 2010 (UTC)[reply]

The Conway reference, [3], page 21, section 2.2 says:

The kissing numbers in other dimensions. More generally we may define the kissing number (usually denoted by τ) of a sphere packing in any dimension to be the number of spheres that touch one sphere. For a lattice packing τ is the same for every sphere, but for an arbitrary packing τ may vary from one sphere to another. Other names for τ that have been used are Newton number (after the originator of the problem), contact number, coordination number of ligancy (the last being chemist's terms.)

So anyway, it looks like kissing number isn't the maximum itself, but a property of a given packing. This ought to be written in to the article. I'd try but not really my domain of confidence. :) 75.146.178.58 (talk) 21:41, 10 July 2010 (UTC)[reply]

I also notice that Kissing number redirects here which actually is called Kissing number problem, which is the content of the article, but I'll try adding the more general definition. 75.146.178.58 (talk) 21:48, 10 July 2010 (UTC)[reply]

My question is : Are the coordinates of centers of hyperspheres for the lowest bounds of certain dimension 4<n<9 known (40, 72, ...)?
I've only found coords for n=1,2,3,4,8,24 ... Thanks  — Preceding unsigned comment added by 77.38.2.194 (talk) 09:48, 2 December 2012 (UTC)[reply]

Which ones are "tight"?

It would be good for the article to say which ones are tight - in the sense that there is no slack. The two-dimensional case is tight, but three and four are not. IIRC, 8 and 24 are tight, but I'm not sure. Bubba73 ^{You talkin' to me?} 04:32, 21 March 2016 (UTC)[reply]

Inconsistency

The intro paragraph of this page is currently inconsistent:

"In geometry, a kissing number is defined as the greatest number of non-overlapping unit spheres that can be arranged such that they each touch a common unit sphere. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another."

The first sentence describes a property of a space while the second sentence describes a property of a particular sphere within a particular sphere packing (within a particular space). I am going to make both possible notions clear and distinct, but if it only is supposed to be one, feel free to correct.Jess_Riedel (talk) 15:43, 30 May 2020 (UTC)[reply]

Update

if anyone is interested, they can update the known bounds with these two sources: ^[1] and ^[2] — Preceding unsigned comment added by Dintre (talk • contribs) 20:27, 30 March 2023 (UTC)[reply]

References

These appear not to have been peer-reviewed and published, so they do not yet meet Wikipedia's standards for reliable sources. —David Eppstein (talk) 22:14, 30 March 2023 (UTC)[reply]

Here's an arXiv link to the first one. Henry Cohn's page has already been updated with these sources, FWIW. Double sharp (talk) 06:54, 14 December 2023 (UTC)[reply]

[1] ttps://www.semanticscholar.org/paper/Solving-clustered-low-rank-semidefinite-programs-Laat-Leijenhorst/b5e34dc768b72620da731874ed2bd1ea2c25cac6

[2] ttps://arxiv.org/abs/2207.08266#

[1]

[2]