Golomb - 2018-04-12

10:07 AM

@JimT: thanks for taking an interst. I'll be posting my latest findings on math.stackexchange.com/questions/2664590 in a few hours. Got to go shopping right now :-(

Wouter M.

2:19 PM

@JimT: as an example for $n=23$, take the 3 sets, with $z=exp(2 \pi i/23)$,
$z^{22}+z^{21}+z^{19}+z^{17}+z^{15}+z^{13}+z^9+z^5+z^4$,
$z^{22}+z^{21}+z^{20}+z^{17}+z^{15}+z^{13}+z^9+z^7+z^3$,
$z^{22}+z^{20}+z^{18}+z^{14}+z^{13}+z^{12}+z^9+z^7+z^3$
multiply each with its complex conjugate to get thrice the same result:
$z^{22}+3 z^{21}+4 z^{19}+2 z^{18}+4 z^{17}+z^{16}+3 z^{15}+2 z^{14}+3 z^{13}+2 z^{12}+2 z^{11}+3 z^{10}+2 z^9+3 z^8+z^7+4 z^6+2 z^5+4 z^4+3 z^2+z+8$
There are 44 such triplets for $n=23$ and, magically, they correspond to the 44 (real) roots of the following 11th degree equations:

Wouter M.

2:38 PM

@JimT: it seems evident that the multiset of pair-wise differences is palindromic

{0^6, 1^3, 2^2, 3^3, 4^3, 5^2, 6^2, 7^2, 8^2, 9^3, 10^3, 11^2, 12^3}, as is the equation for the square of the abs value

$z^{22}+3 z^{21}+4 z^{19}+2 z^{18}+4 z^{17}+z^{16}+3 z^{15}+2 z^{14}+3 z^{13}+2 z^{12}+2 z^{11}+3 z^{10}+2 z^9+3 z^8+z^7+4 z^6+2 z^5+4 z^4+3 z^2+z+8$

Wouter M.

4:45 PM

@JimT: if it's of interest, I just found the 42 'doublets' of the n=29 case with 6 elements (your 'k=6').
the first doublet is
z^17 + z^20 + z^22 + z^26 + z^27 + z^28,
z^17 + z^19 + z^21 + z^22 + z^27 + z^28
both giving the same absolute value
6 + 2 z + 2 z^2 + z^3 + z^4 + 2 z^5 + 2 z^6 + z^7 + z^8 + z^9 + z^10 + z^11 + z^18 + z^19 + z^20 + z^21 + z^22 + 2 z^23 + 2 z^24 + z^25 + z^26 + 2 z^27 + 2 z^28
and all 42 doublets are generated by the following 3 equations of degree 14:
28604731 - 214777308 x + 629757220 x^2 - 996418270 x^3 + 975143166 x^4 - 635610130 x^5 + 288350157 x^6 - 93425975 x…

JimT

7:02 PM

I see. One way of approaching this could be to introduce a "generating" function for any subset A = {a_1,..., a_k} as f_A(z) = \sum a_j z^j . Then for A and B such that their multisets of pairwise differences coincide we will have f_A(z)f_A(z^{-1}) = f_B(z)f_B(z^{-1}).

As for the relation to the Golomb rulers, it is restricted to only some of the examples, so generally this problem of yours is not closely related to GR. As I mentioned, if for some n = k^2-k+1 there exists a perfect modular Golomb ruler modulo n, then for k > 3 it should be pretty easy to show that there exist the "doublets" your problem is asking about. I haven't really looked closely into it because not too many prime numbers n are of the form k^2-k+1.

I think it would be advisable if we formulate the main conjecture that is being proposed. Something like this: for any number n greater than 11 there exist two non-equivalent (under dihedral group D_n) sets A and B of vectors/vertices of regular n-gon such that the sums of vectors in A and B have the same length. Is that what we suspect here?

Wouter M.

7:34 PM

Close, but not complete. Still need to account for the symmetry 0 <-> 1 induced by the fact that the sum of all n-th complex roots of 1 equals 0.

Maybe that has to do with the palindromic property of the absolute values?

JimT

Well, we can say "non-equivalent and non-complementing"... smth like that.

Wouter M.

yes, that covers it.

JimT

Palindromic property? you mean the fact that the multiset of all {a_i-a_j} is symmetric in Z_n? but that is true for any multiset of pairwise differences -- a_i - a_j = -(a_j - a_i)

Wouter M.

where are the pair-wise differences in "6 + 2 z + 2 z^2 + z^3 + z^4 + 2 z^5 + 2 z^6 + z^7 + z^8 + z^9 + z^10 + z^11 + z^18 + z^19 + z^20 + z^21 + z^22 + 2 z^23 + 2 z^24 + z^25 + z^26 + 2 z^27 + 2 z^28 "?

JimT

In your example A = {17, 20, 22, 26, 27, 28} and B = {17, 19, 21, 22, 27, 28}, or A = {0, 3, 5, 9, 10, 11}, B = {0, 2, 4, 5, 10, 11}. Multiset of pairwise differences is {0^6, 1^2, 2^2, 3, 4, 5^2, 6^2, 7, 8, 9, 10, 11, 18, 19, 20, 21, 22, 23^2, 24^2, 25, 26, 27^2, 28^2}. Which is a multiset representation of that polynomial, if we exclude zeros. Symmetry of this multiset in Z_29 is what we are discussing. Alas, for any subset X the multiset of its pairwise differences is symmetric.

Wouter M.

7:51 PM

I see it now.
Is there a way to count them apart from brute force enumeration?

JimT

Do you mean count the doublets/triplets etc?

Wouter M.

Yes. Since the total number of black-white bracelets are given by the dihedral neclace polynomial, we only need to subtract the overcounting of doublets and triplets and we get the # of different absolute values of the root-sums.

JimT

It's possible but I think we should start with something simpler -- which might in turn give us the approach to the larger problem. Namely, let us prove the "doublet existence conjecture" - the one I formulated above. I think this would be a very good start and something real to "publisize" as well. :)

I think we should introduce some notation and terminology. Something to call/denote the numbers we are computing etc. Will make it easier for is to write it.

Wouter M.

Ok. The devil's advocate asks: "can't there be a prime >13 that behaves like 5 or 7 having no doublets or triplets"?

Notation: z= exp( 2 pi I/n) ; bracelets are noted as A = {0, 3, 5, 9, 10, 11}, B = {0, 2, 4, 5, 10, 11} meaning A=1+z^3+z^5+z^9+z^10+z^11 etc.

JimT

Exactly. But we can skip "triplets" terminology for now - any "tuplet" can be considered as giving us an example of a doublet , so we ask "is it true that for any n > 11 there exist two subsets A and B which are not equivalent under D_n and non-complementing, with the sum of their elements having the same absolute value", or simply " a doublet". Do you by any chance have longer tables of values for prime n?

Gotta leave the office soon. Will think more on that later tonight. What time zone you in?

Wouter M.

8:09 PM

calculation of n=23 took overnight. For n=29, I only checked for bracelets of upto 6 terms. Going to up towards k=14 might take loooong. ;-)

I'm in GMT+2 : Europe.

JimT

Sheesh... perhaps we gotta come up with some better computational approach... if there is one.

Wouter M.

yes, that's where the fun is, nah?

JimT

I am in Boston, USA; GMT (-5), you are 7 hours ahead of me. OK, gotta run. Talk to you later.

Wouter M.

see you Tim.

Transcript for

$Mathematics$ Golomb