A092237 - OEIS

%I #51 Jan 05 2026 13:34:25

%S 0,1,0,12,4,27,42,112,72

%N Maximum number of intercalates in a Latin square of order n.

%C An intercalate is a 2 X 2 subsquare of a Latin square. a(10) >= 125, a(11) >= 172, a(12) >= 324.

%C 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

%C 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

%C a(2^n-1) = 42*A006096(n) for n > 2. - _Eduard I. Vatutin_, Apr 23 2025

%C 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

%C From _Eduard I. Vatutin_, Jul 01 2025: (Start)

%C Table showing minimums and maximums:

%C   order                      | 1 2 3  4 5  6  7   8   9    10    11    12    13    14    15    16    17    18    19

%C   min number of intercalates | 0 1 0  4 0  0  0   0   0     0     0     0     0     0     0     0     0     0     0

%C   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)

%C .

%C   order                      |      20    21     22    23     24     25     26    27     28 29

%C   min number of intercalates |       0     0      0     0      0      0   <=15     0    <=1  0

%C   max number of intercalates |  >=1500 >=884 >=1497 >=983 >=1872 >=1700 >=2197 >=648 >=2940  ? (this sequence)

%C (End)

%D I. Wanless, Private communication, 2003.

%H R. Bean, <a href="https://www.researchgate.net/publication/2416446_Critical_Sets_in_Latin_Squares_and_Associated_Structures">Critical sets in Latin squares and associated structures</a>, Ph.D. Thesis, The University of Queensland, 2001.

%H K. Heinrich and W. Wallis, <a href="https://doi.org/10.1007/BFb0091822">The maximum number of intercalates in a Latin square</a>, Combinatorial Math. VIII, Proc. 8th Australian Conf. Combinatorics, 1980, 221-233.

%H Eduard I. Vatutin, <a href="/A092237/a092237_1.txt">Proving list, minimum number of intercalates (best known examples)</a>.

%H Eduard I. Vatutin, <a href="/A092237/a092237_2.txt">Proving list, maximum number of intercalates (best known examples)</a>.

%H Eduard I. Vatutin, <a href="https://vk.com/wall162891802_3015">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</a> (in Russian).

%H Eduard Vatutin, Jia Wei-Ting, Jun Chi Ma, Qiang Miao, Maxim Manzyuk, Natalia Kukushkina, Ilya Kurochkin, and Alexander Albertian, <a href="https://doi.org/10.1007/978-3-032-13127-0_33">Construction of Intercalate Number Spectra in Latin Squares of Orders 18-28 Using Distributed Parallel Software Implementations</a>, Supercomputing (RuSCDays 2025) 462-474. See references.

%H <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>.

%F 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

%Y Cf. A006096, A016152, A091323, A090741, A383368.

%K hard,nonn,more

%O 1,4

%A _Richard Bean_, Feb 17 2004