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

Hi everyone. I need to pick a set of 65 points p(x,y,z) in a 3D space of 274625 points; as the set picked should provide the maximum possible minimum Hamming distance. (Consider the Hamming bound for sphere packing). Can anybody please help me with developing an algorithm for naming these 65 discrete points? Thanks, Tan

share|improve this question
2  
Have you read the FAQ, by any chance? –  David Roberts Aug 15 '12 at 12:26
2  
$274625 = 65^3$. If it's just a $65 \times 65 \times 65$ cube then the optimal packing of $65$ points with respect to Hamming distance is clear (see also D.Roberts' comment). –  Noam D. Elkies Aug 15 '12 at 12:30
1  
If the $x,y,z$ are selected from the same set of 65 alternatives, then it seems clear to me that you want to use the 65 points on the 3D-diagonal, i.e. select the points of the form $(x,x,x)$. There are 65 of them, and the minimum Hamming distance between two points within this set is three. As any pair of points has Hamming distance at most three, this cannot be beaten. Or did you want to ask something else? –  Jyrki Lahtonen Aug 15 '12 at 13:50
    
Lahtonen Thanks for your response. I guess i couldn't express it clearly. There are 65^3 alternatives (not 65) to chose from, and I need to chose the best 65 which satisfy the max minimum Ham.Dist. x,y,z are the dimensions of each point (so 3D). –  Tan Aug 16 '12 at 8:31
    
Elkies thanks for your response. I get your approach, but the space is not a cube, but a space of 65^3 points in their densest (assumingly a sphere) form. I need to find out the (or one of the) set of 65 points among all within this packing, satisfying the max.minimal ham.dist. So the members of the set should be 1)at a maximum distance from each other, and 2)reside in the packing. Hope this better explains my goal. I also checked the FAQ but couldn't really get D.Roberts' comment. –  Tan Aug 16 '12 at 8:48

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.