NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/sci/math/17240

Internet Message Format | 1992-12-21 | 3.1 KB

Path: sparky!uunet!europa.asd.contel.com!howland.reston.ans.net!paladin.american.edu!news.univie.ac.at!hp4at!mcsun!uknet!pavo.csi.cam.ac.uk!camcus!cet1
From: [e-mail] (C.E. Thompson)
Newsgroups: sci.math
Subject: Re: Tiling problem
Message-ID: <[e-mail]>
Date: 20 Dec 92 22:53:30 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]> <israel
Sender: [e-mail] (USENET news)
Organization: U of Cambridge, England
Lines: 53
Nntp-Posting-Host: grus.cus.cam.ac.uk

In article <[e-mail]>, [e-mail]
(Robert B. Israel) writes:
|>
|> As a matter of fact, there *is* something odd going on.  A close look at
|> this solution shows that all the rows are cyclic permutations of
|> 001101a101100, where "a" is either 0 or 1, each row being displaced 5
|> places to the left from the previous one.  If you write one of these
|> 13-tuples as <c_i>_{i=0..12}, it satisfies the condition that for all
|> i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
|> same (considering the subscripts mod 13).  Thus such a 13-tuple generates
|> a square that works (with periodic boundary condition).  The only 13-tuples
|> for which this works are these two and those obtained from them by cyclic
|> permutation and interchanging 1 and 0.  I also tried shifts other than 5
|> (so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
|> never to be all the same).  No more examples except for b=8 (which is
|> equivalent to b=5 by left<->right symmetry).  Unfortunately, there are no
|> 14-, 15-, 16- or 17-tuples with the analogous properties either.

It really looks as thought there ought to be some significance in the fact
that 001101a101100 is the pattern of quadratic residues mod 13 (a at the
point 0 mod 13), and in the fact that 5 and 8 are the square roots of -1
mod 13. But naive attempts to use the same rules for larger primes don't
work. (They do work for N=5, 01a10 shifted 2 for each new row.)

|> I don't think that my search strategy has any inherent bias towards
|> solutions with any particular regularity or periodicity.  I tried running
|> the 13 x 13 square again, with the following result:
|>
|> 1011010011010
|> 0001111010110
|> 0111001000011
|> 1100011101010
|> 1001010100111
|> 0101110001101
|> 0000100111011
|> 1010111100001
|> 0110010110101
|> 0011001101100
|> 111010*000110
|> 1000001011101
|> 1101100110000
|>
|> If there's structure here, it's certainly more subtle than last time.
|> I haven't checked whether this satisfies the periodic boundary condition.

Not quite. But if the 1 at the point which I have taken the liberty of
marking with a * is replaced by a 0, then it does satisfy the stronger
periodic constraints. This rather suggests that most (all?) 13x13 solutions
of the weaker problem are "not far" from a solution of the stronger one.

Chris Thompson
JANET:    [e-mail]
Internet: [e-mail]