OFFSET
1,4
COMMENTS
An intercalate is a 2 X 2 subsquare of a Latin square. a(10) >= 125, a(11) >= 172, a(12) >= 324.
a(13) >= 216, a(14) >= 391, a(15) >= 630, a(16) >= 960, a(17) >= 736, a(18) >= 729, a(19) >= 472, a(20) >= 1500, a(21) >= 1026, a(22) >= 1497, a(23) >= 983, a(24) >= 2736, a(25) >= 1888, a(26) >= 2197, a(27) >= 648, a(28) >= 2940. - Eduard I. Vatutin, Mar 02 2025, updated Nov 26 2025
If, in theory, all unordered pairs of rows and columns form intercalate in their intersection, total number of intercalates will be (n*(n-1))^2, so a(n) <= (n*(n-1))^2, a(n) is asymptotically less than O(n^4). In practice a(n) << (n*(n-1))^2. - Eduard I. Vatutin, Mar 11 2025
a(2^n-1) = 42*A006096(n) for n > 2. - Eduard I. Vatutin, Apr 23 2025
Due to existence of the pine Latin squares for even orders N=2n, a(2n) >= A383368(n). Pine Latin squares exist for all even orders, so a(N) >= (2k)^2 * (2k + 1) for N=4k and a(N) >= (2k+1)^3 for N=4k+2. Therefore, asymptotically maximum number of intercalates in Latin squares of even orders N greater or equal than o(k1*N^3), where k1 = 1/8. - Eduard I. Vatutin, Apr 30 2025
From Eduard I. Vatutin, Jul 01 2025: (Start)
Table showing minimums and maximums:
order | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
min number of intercalates | 0 1 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
max number of intercalates | 0 1 0 12 4 27 42 112 72 >=125 >=172 >=324 >=208 >=391 >=630 >=960 >=736 >=729 >=472 (this sequence)
.
order | 20 21 22 23 24 25 26 27 28 29
min number of intercalates | 0 0 0 0 0 0 <=15 0 <=1 0
max number of intercalates | >=1500 >=884 >=1497 >=983 >=1872 >=1700 >=2197 >=648 >=2940 ? (this sequence)
(End)
REFERENCES
I. Wanless, Private communication, 2003.
LINKS
R. Bean, Critical sets in Latin squares and associated structures, Ph.D. Thesis, The University of Queensland, 2001.
K. Heinrich and W. Wallis, The maximum number of intercalates in a Latin square, Combinatorial Math. VIII, Proc. 8th Australian Conf. Combinatorics, 1980, 221-233.
Eduard I. Vatutin, Proving list, minimum number of intercalates (best known examples).
Eduard I. Vatutin, Proving list, maximum number of intercalates (best known examples).
Eduard I. Vatutin, About interconnection between maximum number of intercalates in Latin squares of order N=2^n-1 and Gaussian binomial coefficients [n,3] for q=2 (in Russian).
Eduard Vatutin, Jia Wei-Ting, Jun Chi Ma, Qiang Miao, Maxim Manzyuk, Natalia Kukushkina, Ilya Kurochkin, and Alexander Albertian, Construction of Intercalate Number Spectra in Latin Squares of Orders 18-28 Using Distributed Parallel Software Implementations, Supercomputing (RuSCDays 2025) 462-474. See references.
FORMULA
If n is a power of 2, a(n) = n^2*(n-1)/4 = A016152(log2(n)); if n is one less than a power of 2, a(n) = n*(n-1)*(n-3)/4 = A006096(log2(n+1))*42. - updated by Eduard I. Vatutin, Jun 28 2025
CROSSREFS
KEYWORD
hard,nonn,more
AUTHOR
Richard Bean, Feb 17 2004
STATUS
approved