33
$\begingroup$

This is based on another thread. For $m,n\in \mathbb N$, let $f(m,n)$ be the minimum number of squares with integer sides needed to tile a $m\times n$ rectangle. Recently, a table of values for $n\le m\le 85$, obtained by what seems to be a brute force search, has been put online here.

The table looks quite fuzzy, but if we restrict it to values of coprime $m,n$ such that $2n\ge m\ge n$, there is surprisingly little fluctuation. For convenience, the following table gives $f(m,n)$ in reverse order, showing in row $n$ the values for $m=n-1,n-2,...,\lbrace n/2\rbrace$ but putting "o" wherever $(m,n)>1$.

(The number following $m$ is $ g(m):=\frac{\log(m\sqrt{5})}{\log(\phi)}$ where $\phi=\frac{\sqrt{5}+1}2$, see below.) 

 3 :  3.955  [ 3]
 4 :  4.553  [ 4]
 5 :  5.016  [ 5, 4]
 6 :  5.395  [ 5, o]
 7 :  5.716  [ 5, 5, 5]
 8 :  5.993  [ 7, o, 5]
 9 :  6.238  [ 7, 6, o, 6]
10 :  6.457  [ 6, o, 6, o]
11 :  6.655  [ 6, 7, 6, 6, 6]
12 :  6.836  [ 7, o, o, o, 6]
13 :  7.002  [ 7, 6, 7, 7, 6, 6]
14 :  7.156  [ 7, o, 7, o, 7, o]
15 :  7.299  [ 7, 8, o, 7, o, o, 8]
16 :  7.433  [ 7, o, 8, o, 7, o, 7]
17 :  7.559  [ 8, 8, 7, 8, 7, 7, 7, 8]
18 :  7.678  [ 8, o, o, o, 7, o, 7, o]
19 :  7.791  [ 7, 9, 7, 7, 7, 7, 7, 7, 7]
20 :  7.897  [ 9, o, 7, o, o, o, 7, o, 8]
21 :  7.999  [ 8, 7, o, 9, 8, o, o, 7, o, 7]
22 :  8.095  [ 8, o, 8, o, 8, o, 8, o, 8, o]
23 :  8.188  [ 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8]
24 :  8.276  [ 8, o, o, o, 9, o, 8, o, o, o, 7]
25 :  8.361  [ 8, 8, 8, 8, o, 8, 8, 9, 8, o, 8, 8]
26 :  8.442  [ 8, o, 8, o, 8, o, 8, o, 9, o, 8, o]
27 :  8.521  [ 8,10, o, 8, 8, o, 8, 8, o, 8, 8, o, 8]
28 :  8.596  [ 8, o,10, o, 9, o, o, o, 8, o, 8, o, 8]
29 :  8.669  [ 9, 8, 8,10,10, 9, 9, 8, 9, 8, 8, 8, 9, 8]
30 :  8.740  [ 9, o, o, o, o, o, 9, o, o, o, 8, o, 9, o]
31 :  8.808  [ 8, 8, 8,10, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 8]
32 :  8.874  [ 9, o, 8, o, 8, o, 9, o, 9, o, 8, o, 8, o, 9]
33 :  8.938  [ 9, 9, o, 9, 8, o, 8,10, o, 9, o, o, 8, 8, o, 9]
34 :  9.000  [ 9, o, 9, o, 9, o, 9, o, 8, o, 9, o, 8, o, 8, o]
35 :  9.060  [ 8, 9,10, 8, o, 9, o, 9, 8, o, 8, 9, 9, o, o, 8, 9]
36 :  9.119  [ 9, o, o, o,10, o,10, o, o, o, 9, o, 9, o, o, o,10]
37 :  9.176  [ 9, 9, 9, 9, 8,10, 9, 8, 9, 9, 9, 9, 8, 9, 8, 9, 8, 8]
38 :  9.231  [ 9, o, 9, o, 9, o, 9, o,10, o, 9, o, 9, o, 9, o,10, o]
39 :  9.285  [ 9, 9, o, 9, 9, o,10, 9, o, 9, 9, o, o, 9, o, 9, 9, o, 9]
40 :  9.338  [ 9, o, 9, o, o, o, 9, o, 9, o, 8, o, 9, o, o, o, 9, o, 8]
41 :  9.389  [ 9, 9, 9, 9,11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
42 :  9.439  [ 9, o, o, o, 9, o, o, o, o, o,10, o,10, o, o, o,10, o,10, o]
43 :  9.488  [ 9, 9, 9, 9, 9, 9,10,10, 9, 9, 9, 9, 9, 9, 9, 9,10, 9, 9, 9, 9]
44 :  9.536  [ 9, o, 9, o, 9, o, 9, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o, 9]
45 :  9.582  [10, 9, o,10, o, o, 9, 9, o, o, 9, o, 9, 9, o,10, 9, o, 9, o, o, 9]
46 :  9.628  [ 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o, 9, o]
47 :  9.673  [ 9, 9, 9,11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,10, 9, 9, 9, 9, 9, 9, 9, 9]
48 :  9.716  [10, o, o, o, 9, o, 9, o, o, o,10, o,10, o, o, o, 9, o, 9, o, o, o, 9]
49 :  9.759  [ 9, 9, 9, 9,10,10, o, 9, 9, 9, 9, 9, 9, o, 9,10,10, 9, 9,10, o, 9, 9, 9]
50 :  9.801  [10, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o, o, o, 9, o, 9, o, 9, o, 9, o]
51 :  9.842  [ 9,10, o, 9,10, o,10, 9, o,10,10, o, 9,10, o, 9, o, o, 9,10, o,10,10, o, 9]
52 :  9.883  [10, o,11, o, 9, o,10, o,10, o, 9, o, o, o, 9, o,10, o, 9, o, 9, o,10, o,11]
53 :  9.922  [10, 9, 9,11, 9,10,10, 9,10,11,10, 9,10, 9,10,10,11,10, 9, 9, 9, 9, 9,11,11, 9]
54 :  9.961  [10, o, o, o, 9, o,10, o, o, o, 9, o, 9, o, o, o, 9, o, 9, o, o, o, 9, o,10, o]
55 :  9.999  [10,10,10,10, o, 9, 9, 9, 9, o, o, 9,10, 9, o, 9, 9, 9,10, o, 9, o,10, 9, o, 9, 9]
56 :  10.03  [ 9, o, 9, o,10, o, o, o, 9, o,10, o,11, o,10, o,10, o, 9, o, o, o,10, o, 9, o, 9]
57 :  10.07  [10,10, o,10, 9, o,10,10, o,10, 9, o, 9,10, o,10,10, o, o, 9, o,10, 9, o,10, 9, o,10]
58 :  10.11  [10, o,10, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o]
59 :  10.14  [10,10, 9, 9,10,11, 9, 9, 9,10,10, 9, 9,10, 9, 9, 9,10, 9, 9,10, 9,10, 9, 9, 9, 9, 9,10]
60 :  10.18  [10, o, o, o, o, o,11, o, o, o,10, o,10, o, o, o,11, o, 9, o, o, o,10, o, o, o, o, o, 9]
61 :  10.21  [10, 9,10,10,10,10, 9, 9,10,10, 9,11,10,10,10,10, 9, 9,10,10, 9,10, 9, 9,10, 9,10, 9, 9, 9]
62 :  10.24  [10, o,10, o,10, o,10, o,10, o,10, o,11, o,11, o,10, o,11, o,10, o,10, o,10, o,10, o,10, o]
63 :  10.28  [10,10, o,10,10, o, o,10, o,10,10, o,10, o, o,10,10, o,10,10, o,10,10, o,10,10, o, o,10, o,10]
64 :  10.31  [10, o,10, o,10, o,10, o,11, o,11, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10]
65 :  10.34  [10,10,10,10, o,10,10,10,10, o,10,10, o,10, o,11,10,10,10, o,10,10,10,10, o, o,10,10,11, o,10,10]
66 :  10.37  [10, o, o, o,10, o,10, o, o, o, o, o,10, o, o, o, 9, o,10, o, o, o,10, o,10, o, o, o, 9, o, 9, o]
67 :  10.40  [10,10,10,10,10,10,11,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10]
68 :  10.44  [10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o, o, o,10, o,10, o,10, o,10, o,10, o,10, o,11, o,10]
69 :  10.47  [10,10, o,10,11, o,10, 9, o,10,10, o,10,11, o,11,11, o,10,11, o,10, o, o,10,10, o, 9, 9, o,10, 9, o, 9]
70 :  10.50  [11, o,10, o, o, o, o, o,10, o,10, o,10, o, o, o,11, o,10, o, o, o,10, o, o, o,10, o,10, o,10, o,10, o]
71 :  10.53  [10,10,10,12,10,10,10,10,10,11,10,12,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10]
72 :  10.55  [10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,10]
73 :  10.58  [10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
74 :  10.61  [10, o,10, o,10, o,10, o,10, o,10, o,11, o,11, o,10, o,11, o,10, o,10, o,10, o,10, o,11, o,10, o,10, o,10, o]
75 :  10.64  [10,11, o,10, o, o,10,10, o, o,10, o,10,10, o,10,10, o,10, o, o,10,11, o, o,10, o,10,10, o,10,10, o,10, o, o,10]
76 :  10.67  [10, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o,10, o, o, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10, o,10]
77 :  10.69  [10,10,10,10,10,11, o,10,10,12, o,10,11, o,10,11,12,10,10,10, o, o,10,12,12,10,10, o,10,10,10,10, o,10, o,12,10,10]
78 :  10.72  [11, o, o, o,10, o,10, o, o, o,10, o, o, o, o, o,11, o,10, o, o, o,11, o,11, o, o, o,11, o,10, o, o, o,11, o,10, o]
79 :  10.75  [11,10,10,11,11,10,10,10,10,11,11,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,11,11,10,10,10,11,10,10,10,11,10,10,10]
80 :  10.77  [10, o,10, o, o, o,10, o,10, o,12, o,10, o, o, o,10, o,11, o,11, o,10, o, o, o,10, o,11, o,10, o,10, o, o, o,10, o,10]
81 :  10.80  [10,10, o,12,11, o,10,10, o,10,10, o,10,12, o,10,10, o,10,10, o,10,10, o,10,10, o,11,11, o,10,11, o,10,10, o,10,10, o,10]
82 :  10.82  [10, o,11, o,11, o,11, o,10, o,11, o,11, o,10, o,10, o,11, o,10, o,10, o,10, o,10, o,11, o,10, o,11, o,10, o,10, o,10, o]
83 :  10.85  [10,10,10,10,10,11,10,10,10,10,10,10,10,10,11,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,10,10,10]
84 :  10.87  [10, o, o, o,10, o, o, o, o, o,10, o,10, o, o, o,10, o,10, o, o, o,11, o,10, o, o, o,10, o,10, o, o, o, o, o,10, o, o, o,10]
85 :  10.90  [10,10,11,10, o,12,11,10,10, o,10,12,10,10, o,11, o,10,10, o,10,11,11,10, o,10,11,11,10, o,10,10,10, o, o,10,11,10,10, o,10,10]

For a Fibonacci rectangle, we obviously have $f(F_{k+1},F_k)\le k$, and it seems straightforward to show that this bound is sharp. But is this really trivial?

It looks like under the above restrictions on $m$ and $n$, the values of $f(m,n)$ are very close to $g(m)$, more precisely $$\boxed{\lfloor g(m)\rfloor -1\le f(m,n)\le \lceil g(m)\rceil +1}.$$ Is it possible that in the minimal tilings, patterns like in a 'Fibonacci rectangle tiling' occur frequently?

Note that it is already known or at least plausible from the article quoted in the first thread that $f(m,n)\sim g(m)$.

What about $f(m,n)$ if the rectangle sides are not coprime? Obviously $f(km,kn)\le f(m,n)$ for $k\in \mathbb N$. In the range of the table, there is equality everywhere.

Is anything known concerning the conjecture $f(km,kn)= f(m,n)$?

Moreover, does there even exist a minimal tiling of a $km\times kn$ rectangle such that not all square sides are multiples of $k$?

For $m> n$, let’s call a $m\times n$ rectangle reducible if $f(m,n)=f(n,m-n)+1$. This means there is a minimal tiling such that the biggest square has side $n$. (There may exist other minimal tilings also, though I'd rather doubt it).

Using the same order as above, I have kept in row $m$ only those $n$’s for which the $m\times n$ rectangle is reducible and put "o" where it is not:

 3 : [ 2]
 4 : [ 3]
 5 : [ 4, 3]
 6 : [ o, 4]
 7 : [ o, 5, 4]
 8 : [ o, 6, 5]
 9 : [ o, 7, 6, 5]
10 : [ o, 8, 7, 6]
11 : [ o, 9, 8, 7, 6]
12 : [ o, o, 9, 8, 7]
13 : [ o, o,10, 9, 8, 7]
14 : [ o, o,11,10, 9, 8]
15 : [ o, o,12,11,10, 9, 8]
16 : [ o, o,13,12,11,10, 9]
17 : [ o, o, o,13,12,11,10, 9]
18 : [ o, o, o,14,13,12,11,10]
19 : [ o, o, o, o, o,13,12,11,10]
20 : [ o, o, o,16,15,14,13,12,11]
21 : [ o, o, o,17,16,15,14,13,12,11]
22 : [ o, o, o,18,17,16, o,14,13,12]
23 : [ o, o, o,19,18,17,16, o,14,13,12]
24 : [ o, o, o, o,19,18,17,16,15,14,13]
25 : [ o, o, o, o,20,19,18,17,16,15,14,13]
26 : [ o, o, o, o, o,20,19,18,17,16,15,14]
27 : [ o, o, o, o, o,21,20,19,18,17,16,15,14]
28 : [ o, o, o, o,23,22,21,20,19,18,17,16, o]
29 : [ o, o, o, o,24,23, o,21,20,19,18,17,16,15]
30 : [ o, o, o, o, o,24,23,22,21,20,19,18,17,16]
31 : [ o, o, o, o, o, o, o, o, o,21,20,19,18,17,16]
32 : [ o, o, o, o, o,26,25,24,23,22,21,20,19,18,17]
33 : [ o, o, o, o, o,27, o,25,24,23,22,21,20,19,18,17]
34 : [ o, o, o, o, o, o,27,26, o,24,23,22,21,20,19,18]
35 : [ o, o, o, o, o, o,28,27, o,25,24,23,22,21,20,19,18]
36 : [ o, o, o, o, o, o, o,28,27,26,25,24,23,22,21,20,19]
37 : [ o, o, o, o, o,31, o, o,28,27,26,25,24,23, o,21,20,19]
38 : [ o, o, o, o, o, o, o, o,29, o,27,26,25,24,23,22,21,20]
39 : [ o, o, o, o, o, o,32, o,30,29,28,27,26,25,24,23,22,21, o]
40 : [ o, o, o, o, o, o, o,32, o,30, o,28,27,26,25,24,23,22,21]
41 : [ o, o, o, o, o, o, o, o, o,31,30,29, o,27,26,25,24,23,22,21]
42 : [ o, o, o, o, o, o, o,34,33,32,31,30,29,28,27,26,25,24,23,22]
43 : [ o, o, o, o, o, o, o,35, o, o,32,31, o,29,28,27,26,25, o,23,22]
44 : [ o, o, o, o, o, o, o,36, o,34,33,32,31, o,29,28,27,26,25,24,23]
45 : [ o, o, o, o, o, o, o, o,36,35, o,33,32,31,30,29,28,27,26,25,24,23]
46 : [ o, o, o, o, o, o, o,38, o,36,35,34,33,32,31, o,29,28,27,26,25,24]
47 : [ o, o, o, o, o, o, o, o, o, o, o, o,34,33,32,31, o,29,28,27,26,25,24]
48 : [ o, o, o, o, o, o, o, o,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25]
49 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,35,34,33,32,31,30,29,28,27,26,25]
50 : [ o, o, o, o, o, o, o, o, o,40, o,38,37,36,35,34, o,32,31,30,29,28,27,26]
51 : [ o, o, o, o, o, o, o, o, o,41,40,39, o,37,36,35,34,33,32,31,30,29,28,27,26]
52 : [ o, o, o, o, o, o, o, o, o, o, o,40,39,38, o,36,35,34,33,32,31,30,29,28,27]
53 : [ o, o, o, o, o, o, o, o, o,43, o, o,40, o,38,37,36,35,34,33,32,31, o,29,28,27]
54 : [ o, o, o, o, o, o, o, o, o, o, o,42, o,40,39,38,37,36,35,34,33,32,31,30, o,28]
55 : [ o, o, o, o, o, o, o, o, o,45,44, o, o, o,40, o, o,37, o,35,34,33,32,31,30,29,28]
56 : [ o, o, o, o, o, o, o, o, o,46, o,44,43,42,41,40,39,38,37,36,35,34,33,32,31, o,29]
57 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,43, o,41,40,39,38,37,36,35, o,33,32,31,30,29]
58 : [ o, o, o, o, o, o, o, o, o,48,47,46,45, o,43,42,41,40,39,38,37,36,35,34, o,32, o,30]
59 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,45, o, o, o,41,40, o, o,37,36,35,34,33,32,31,30]
60 : [ o, o, o, o, o, o, o, o, o, o, o,48,47,46,45,44,43,42, o,40,39,38,37,36,35,34,33,32,31]
61 : [ o, o, o, o, o, o, o, o, o, o, o,49, o,47,46, o, o, o, o,41,40,39, o,37,36,35,34,33,32,31]
62 : [ o, o, o, o, o, o, o, o, o, o, o, o,49, o,47, o,45, o,43,42,41,40,39,38,37,36,35,34,33,32]
63 : [ o, o, o, o, o, o, o, o, o, o, o,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32]
64 : [ o, o, o, o, o, o, o, o, o, o, o,52, o,50,49,48, o,46,45,44,43,42,41,40,39,38,37,36,35,34,33]
65 : [ o, o, o, o, o, o, o, o, o, o, o, o,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37,36,35,34,33]
66 : [ o, o, o, o, o, o, o, o, o, o, o,54, o, o,51,50, o,48,47,46, o,44,43,42,41,40,39,38,37,36,35,34]
67 : [ o, o, o, o, o, o, o, o, o, o, o,55, o, o, o,51, o,49,48,47,46,45,44,43, o,41,40,39,38,37, o, o,34]
68 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,54, o,52,51, o,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35]
69 : [ o, o, o, o, o, o, o, o, o, o, o,57, o,55,54,53,52,51,50,49,48,47,46, o,44, o,42, o,40,39,38,37,36,35]
70 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,56,55,54, o, o,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36]
71 : [ o, o, o, o, o, o, o, o, o, o, o,59, o, o, o,55,54, o,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37,36]
72 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,57,56, o,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37]
73 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,55,54,53,52, o,50,49,48,47,46,45,44,43, o,41,40,39,38,37]
74 : [ o, o, o, o, o, o, o, o, o, o, o,62, o, o,59, o, o,56, o,54,53,52, o,50,49,48,47,46,45, o,43,42,41,40,39,38]
75 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,60, o, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38]
76 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,58,57, o,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41,40,39]
77 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,63, o, o,60, o, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39]
78 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,64, o, o,61,60,59,58,57,56,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41, o]
79 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,61, o, o, o, o, o,55, o,53, o,51,50,49,48,47,46,45,44,43,42,41,40]
80 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,65,64, o, o, o,60, o, o, o,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41]
81 : [ o, o, o, o, o, o, o, o, o, o, o, o, o,67, o, o, o,63, o, o,60,59, o,57,56,55,54, o,52,51,50,49,48,47,46,45,44,43,42,41]
82 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,63,62,61,60, o,58, o, o,55,54, o,52, o,50,49,48,47,46,45,44,43,42]
83 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,59, o,57,56,55, o,53,52,51,50,49,48,47,46,45,44,43,42]
84 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o,69,68, o,66, o,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46, o,44,43]
85 : [ o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,68, o, o,65, o,63,62,61,60,59, o,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43]

The general tendency is clear, but the overall situation looks rather irregular. For some values of $m$, there are much more 'holes' than for others. Any ideas why?

Improve this question
$\endgroup$
11
  • $\begingroup$ A lot of work on this involved finding positive integer solutions to some low complexity linear equations. Allso, some nice consructions can yield small tesellation numbers for large n and m. You might consider which small tilings generate larger ones, throw those cases out, and then see if you can predict the numbers of the remaining cases. Gerhard "Ask Me About System Design" Paseman, 2012.12.14 $\endgroup$
    – Gerhard Paseman
    Dec 14, 2012 at 18:02
  • $\begingroup$ What do you mean by "small tessellation numbers for large n and m"? Do you mean minimal tilings for (km,kn) that are different from those for (m,n)? If so, do you have an example? $\endgroup$
    – Wolfgang
    Dec 14, 2012 at 20:22
  • $\begingroup$ I was trying to figure out a decompsition for the 20 by 19 case. I saw if I used three large squares, I could reduce it to solving 10 by 9. Another three large squares got me to 6 by 4, which then gives 9 squares total for the 20 by 19 rectangle. By iterating the same construction twice, I got a cover for an exponential increase in lengths at a linear cost in numbers of squares. I imagine many cases could follow this pattern. The exceptional cases are what are deserving of study. I hope you find a pattern. Gerhard "Ask Me About System Design" Paseman, 2012.12.14 $\endgroup$
    – Gerhard Paseman
    Dec 14, 2012 at 20:41
  • $\begingroup$ OK, I see. Your construction yields for example the formula $f(2m+2n,m+3n)\le f(m,n)+3$. In your case, m=3, n=2. (I cannot see how you find your initial 3 squares to reduce 20 by 19 to 10 by 9, but never mind.) $\endgroup$
    – Wolfgang
    Dec 14, 2012 at 21:21
  • 5
    $\begingroup$ See also demonstrations.wolfram.com/MinimallySquaredRectangles for tabulations up to 300-by-300. Also at int-e.eu/~bf3/squares/young.txt by way of int-e.eu/~bf3/squares $\endgroup$
    – Gerry Myerson
    Jul 11, 2014 at 1:50

1 Answer 1

Reset to default
10
$\begingroup$

For rectangles with maximum size 760 or less, there is one remaining possible counterexample. The 17-square tiling of the 697x611 is not proven minimal.

697x611
16 1394 1222 723 671 120 551 499 155 69 1 32 87 39 31 8 55 47 344
17 697 611 51 51 119 119 119 119 119 34 68 34 41 82 82 492 41 205 205

I've put 4944 more at Possible Counterexamples to the Minimal Squaring Conjecture.

My original example shows two known ways to divide a 2(7125×7081) rectangle into 20 squares.

20 square divisions

The smallest known dissection of a (7125×7081) rectangle needs 21 squares.

21 square division

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for this counterexample (if it really is one, that is: how exhaustive was your search for what you call "the smallest known dissection"?) And by curiosity: How much CPU time did this take? $\endgroup$
    – Wolfgang
    Jul 9, 2017 at 20:26
  • $\begingroup$ Didn't take me long, I just downloaded all available rectangles from squaring.net and did a simple search. All the rectangles there are based on polyhedral 3-connected graphs, which means that neighboring squares won't be the same size sharing a full edge. There may be a 2-connected based dissection of the smaller rectangle. There seem to be many counterexamples, look up 6815×6759, 6815×6799, 6861×6715, 6951×6803 and the same ×2 at squaring.net. $\endgroup$
    – Ed Pegg Jr
    Jul 9, 2017 at 20:49
  • $\begingroup$ So it becomes only a counterexample if you can exclude the dissections based on 2-connected graphs (which is probably what I call "reducible" tilings somewhere - all that has been a long time ago), right? And if so: good luck, if that search cannot be automatized! BTW great idea to set up a site www.squaring.net . $\endgroup$
    – Wolfgang
    Jul 9, 2017 at 21:05
  • $\begingroup$ Usually a large rectangle with a nice 3-connected solution for relatively prime sides turns out to be optimal. I have dozens of other counterexamples. It's unlikely that all of them have highly elegant 2-connected solutions. 7382×6259 requires 22 squares. ×2 needs 20 squares. $\endgroup$
    – Ed Pegg Jr
    Jul 9, 2017 at 21:29
  • $\begingroup$ Yes I agree with you that it is very unlikely. But so far, not 100% excluded. And of course the 7382×6259 looks even better. $ $ This being said, I just realize that where you say "neighboring squares won't be the same size sharing a full edge", this is potentially a very strong constraint. The (relatively small) examples of optimal tilings I have seen have very often a $1\times k$ rectangle in the middle. If all those are not considered, I have heavy doubts about the optimality. :( $\endgroup$
    – Wolfgang
    Jul 10, 2017 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.