Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There are some natural packing problems that have been asked in mathematics. Some of them are:

1)How many balls can be placed with in a cube?

2)How many equidistant points can be place on the surface of a sphere?

3)How many code points can one have asymptotically for a length n code with minimum distance(itself defined in various ways) d over an alphabet of size q?

There are many other generalizations to packing in spaces of different characteristics.

My question is given a packing, what are some of the most useful (avoiding exhaustive search) techniques available to show that packing is NOT optimal?

share|improve this question
2  
I don't think there are general methods that work for all packings. However, sometimes you can get good results using linear programming bounds. This was used for kissing numbers by Odlyzko (and possibly others), and for lattice packings by Cohn-Elkies and Cohn-Kumar. –  S. Carnahan Aug 20 '13 at 13:38
1  
For the sphere surface case, I am not aware of anything better than equilibrating point charges on the surface with uniformly random initial conditions. Unless there is a better way, it's not clear to me how a given instance of this could be shown to be optimal. –  Steve Huntsman Aug 20 '13 at 13:54
    
@S.Carnahan As I understand linear programming provides upper bounds (please correct if I am wrong). As such they could be used to show sub-optimality of given packing if the bound is tight. –  Turbo Aug 20 '13 at 14:30
    
Also, how many angels can dance on the head of a pin? In his 1667 tract The Reasons of the Christian Religion, Baxter reviews opinions on the materiality of angels from ancient times, concluding: And Schibler with others, maketh the difference of extension to be this, that Angels can contract their whole substance into one part of space, and therefore have not partes extra partes. Whereupon it is that the Schoolmen have questioned how many Angels may fit upon the point of a Needle?". –Richard Baxter –  Will Jagy Aug 20 '13 at 18:35
    
Hmm atleast a million at last count in year book of inventions in $'88$. Come on I think neglecting suboptimal packings is important. Most of the techniques are scattered around. I could not find a coherent list. –  Turbo Aug 20 '13 at 18:36

2 Answers 2

Usually the best way to show a packing is NOT optimal is to construct a better one. You might try various heuristics, or non-exhaustive search methods such as simulated annealing, tabu search, or genetic algorithms.

share|improve this answer
    
A 99.9999% guarantee may not mean anything here due to the number of points involved (even for small dimensions like 40-50). xkcd.com/1161 came to my mind:) –  Turbo Aug 20 '13 at 15:52

My knowledge is limited when it comes to general combinatorial packings. But the kind of problem OP described is important in coding theory, where the difference between proving the existence of a good packing and explicitly constructing it (along with a practical decoding method) can be significant.

Assuming you come up with an error-correcting code and an efficient decoding method, if you would like to know if it's optimal or not as a packing, basically you need a good lower bound on optimality as a packing that potentially shows that you could do better or an upper bound that your code happens to achieve (so you can prove that yours is an optimal example in one sense of optimality). Since you want to show that your code is not optimal, we ignore the latter case.

Assuming that the alphabet size $q$ is fixed and that the parameters you care are the length $n$, number $k$ of codewords, and minimum distance $d$, one trivial way is of course to check all known codes ever constructed that have the same $n$ and $k$ and see if at least one of them has larger minimum distance $d$ than yours (or fix $n$ and $d$ and see if there is a known code that packs more codewords, or fix $k$ and $d$ and check if a known code can achieve them at a shorter length).

Certainly the above statement is trivial and hardly a "mathematical" method for proving that your code is not optimal. But you might be in a situation where no one has come up with explicit constructions for codes that have the exact same $n$ and $k$ (or $n$ and $d$, or $k$ and $d$) as yours. So you need a more general way to mathematically prove that you could do better if you try hard enough.

The Gilbert–Varshamov bound is a well-known, general lower bound on the size $k$ of a code of length $n$ and minimum distance $d$. You can fix a different pair of parameters to show non-optimality, too. Roughly speaking, this bound is proved by showing that there exists a certain greedy algorithm for gathering codewords that gets you at least a certain number of codewords. This "certain number of codewords" is thus interpreted as a lower bound on optimality in terms of codewords because if you have a fewer codewords right now, you should be able to pack more while keeping the same length and minimum distance. There are better lower bounds in coding theory as well. The first few paragraphs of the introduction of the following paper may serve as a very brief summary of lower bounds on optimality of this kind:

P. Gaborit and G. Zémor, Asymptotic improvement of the Gilbert–Varshamov bound for linear codes, IEEE Trans. Inform. Theory, 54 (2008) 3865-3872

For the asymptotic case you specifically mentioned for codes, the asymptotic version of the Gilbert–Varshamov bound (which can be proved by the probabilistic method, i.e., showing that you can draw from a pool of codes an example of certain size with a positive probability) is actually quite a strong lower bound and very hard to achieve by explicit constructions.

So, given an explicit example, a quick and general way to prove its non-optimality is to try common "nonconstructive" techniques and see if you can prove the existence of a better code as a packing because they generally give stronger lower bounds. (I put the word nonconstructive in quotes because what it actually means can be vague.) Of course, the codes that nonconstructive lower bounds say exist typically do not allow for practical decoding. But good lower bounds like the Gilbert–Varshamov bound are an oft-used measure for how close your explicit example is to the hypothetical but sure-to-exist one.

As for general packing problems where it doesn't matter if it's explicit or not, your question seems to be asking if there is a method for proving that you should be able to pack more but can't prove how much. I don't know if there is such a result (although this doesn't mean much because my knowledge of packing is astonishingly poor...). But if exists, it must be proved by a genuinely nonconstructive proof. I'm interested to know if there is such a highly nonconstructive method for some packing problem, too.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.