1 rectángulo <= 4 cuadrados

Question

Hace casi 25 años, un profesor de la Universidad de Indiana me mostró el siguiente problema:

dado un mapa $\mathbb{Z}^2\rightarrow\mathbb{R}$ tal que la suma dentro de cada cuadrado (paralelo a los ejes) es $\leq1$ en valor absoluto, demostrar que la suma dentro de cada rectángulo (paralelo a los ejes) es $\leq4$ en valor absoluto.

Es divertido y no es demasiado difícil de probar. Creo que en su momento pude demostrar que el límite superior se puede mejorar hasta 3,975 - pero eso fue mucho más difícil y no puedo decir ahora que sea seguro. Además, con una búsqueda en el ordenador (el viejo TRS 80) produje un ejemplo que contenía un rectángulo de área $3\frac{1}{3}$ .

Estas son algunas de las preguntas que se me ocurren:

• ¿se puede mejorar el límite superior de 4 (o 3,975?)?
• puede el límite inferior de $3\frac{1}{3}$ ¿se puede mejorar?
• ¿alguna prueba/conjetura sobre el límite óptimo?
• ¿los resultados se extienden a los mapas $\mathbb{R}^2\rightarrow\mathbb{R}$ ¿Siempre que sean lo suficientemente "amables"?
• ¿Son posibles otras generalizaciones de este problema (por ejemplo, diferentes inclinaciones del plano o de otras variedades, o dimensiones más altas)?

Actualización 1 (actualizada el 7 de marzo de 2010) . ¡Vea las respuestas y los comentarios más abajo para ver ejemplos que logran ratios tan altos como 181/48 = 3,7708333...!

Actualización 2 . Aquí está un esquema de la prueba de que 4 es un límite superior. Ahora se conoce un límite de 254/67=3,79104477... (ver respuestas más abajo), pero la prueba para ello necesita ser sembrada con al menos algún límite conocido.

Dado un rectángulo R de tamaño AxB, con A < B, llámalo "delgado" si $B\geq2A$ o "gordo" si $B\leq2A$ (el caso B=2A es irrelevante ya que es la unión de 2 cuadrados). Se pueden dibujar los 4 cuadrados en los lados de R, bien hacia fuera (tamaño del sobre = (2B+A)x(2A+B)), o bien hacia dentro (algunos se derraman por los lados opuestos, tamaño del sobre = (2B-A)xB) - llámese "sobre grande" y "sobre pequeño".

Supongamos que R tiene la suma 4+ $\epsilon$ y que cada cuadrado tiene una suma entre -1 y 1. Tenemos 3 casos, todos ellos ejercicios fáciles de resolver:

(1) para cualquier R, el sobre grande gordo (2A+B)x(2B+A) tendrá suma $\leq-4-3\epsilon$ .

(2) para un R gordo, un sub-rectángulo (2A-B)x(2B-A) de la envolvente pequeña tendrá suma $\leq-4-3\epsilon$ ;

(3) para una R delgada, un sub-rectángulo delgado (B-2A)x(2B-A) de la envoltura pequeña, tendrá suma $\geq4+3\epsilon$ ;

Aplicando cualquiera de (1)+(2), (2)+(1) o (3)+(3) se obtiene un rectángulo de 3Ax3B con suma $\geq4+9\epsilon$ . Al iterar n veces se obtiene un $3^{n}A \times 3^{n}B$ rectángulo con suma $4+9^{n}\epsilon$ . Dicho rectángulo está formado por no más de AxB cuadrados (cada uno de tamaño $3^{n} \times 3^{n}$ ) y por lo tanto, para un n suficientemente grande, uno de los cuadrados tendrá una suma >1. $\square$

Reformulación . Dado un grupo abeliano G y un mapa

f: GxGxGxG -> $\mathbb{R}$ tal que

1) -1<=f(a,b,c,d)<=1 si d*a=c*b (acotación de los cuadrados),

2) f(a,b,c,d)+f(c,b,e,d)=f(a,b,e,d) para todos los a, b, c, d, e en G (aditividad horizontal de los rectángulos),

3) f(a,b,c,d)+f(a,d,c,e)=f(a,b,c,e) para todos los a, b, c, d, e en G (aditividad vertical de los rectángulos),

¿podemos encontrar un mejor límite universal b(G) tal que -b(G) <= f <= b(G)?

Todo el trabajo anterior sobre esta cuestión equivale al resultado 181/48 <= b( $\mathbb{Z}$ ) <= b( $\mathbb{Z}x\mathbb{Z}$ ) <= 254/67

Para los grupos no abelianos quizás se podría generalizar la noción de "cuadrado" elevándola desde G/[G,G].

Answer 1

Una búsqueda informática condujo al siguiente ejemplo de 16x16 con un 7/2 rectángulo en el centro (escalar todo en 1/12):

 0  -3   3   0   0   0   0   0   0   0   0  -6   6   0   0   0
-1   1  -3   0   3   3  -3   0   0  -3   0   6   0  -3   0   0
 4   2   0   0 -12   9  -3   0   0   0   9 -12   0  -3   6   0
-6   0   0   0   6 -12  12  -6   0  12 -12   3   3   2  -2  -6
 6   0   0   0   6   0 -12   6  12 -12   0   3   2  -1  -4  12
-3   0   0   0  -3   2  -2   0  -6   6  -6  12  -5  -7   0   0
 0   0   0   0   3   4  -4  -6   0 -12  12  -6   0  12   0  -6
 0   0   0   0  -6 -12  12   6  12  12 -12  -6   0   0   0   0
 0   9  -6   0   6   2  -2  -4  -2 -10  10   0   5  -9  -2   0
 3  -3   0   0   0   4  -4  -2  -4   4  -4   6   0   4   2  -6
 0  -6   6   0   0   0 -12   6  12 -12   0  -3  -2   1   4   6
-6   0   0   0   6 -12  12   2  -8  12 -12   3   3   0   0  -6
 8   0  -6   4 -12   9   3  -5  -1   0   9  -6  -4   4   0   3
 0   0   0  -4   4   0   0   3  -7   0   3   1  -2  -1  -4   3
-2   0   3  -1   0   3   0  -1   2   0  -6  -1   7   0   0   0
-3   0   6   1   0  -4   0   1  -1  -3   3   0   0   0   0   0 

Actualización Utilizando la observación de Leonid sobre la imposición de la simetría, he aquí un ejemplo más pequeño y simétrico de 13x16 con un rectángulo de 7/2 (escala de 1/4):

 0  0  0  0  1 -1  0  0  0  0 -1  1  0  0  0  0
 1  0  0 -2 -2  4 -1  0  0 -1  4 -2 -2  0  0  1
-2  0  0  2  0 -4  4 -1 -1  4 -4  0  2  0  0 -2
 1  0  0  0  0  0 -4  3  3 -4  0  0  0  0  0  1
 0  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0  0
 0  0  0  0  2  2 -2 -1 -1 -2  2  2  0  0  0  0
 0  0  0  0 -2 -4  4  3  3  4 -4 -2  0  0  0  0
 0  0  0  0  2  2 -2 -1 -1 -2  2  2  0  0  0  0
 0  0  0  0  0  0  0 -1 -1  0  0  0  0  0  0  0
 1  0  0  0  0  0 -4  3  3 -4  0  0  0  0  0  1
-2  0  0  2  0 -4  4 -1 -1  4 -4  0  2  0  0 -2
 1  0  0 -2 -2  4 -1  0  0 -1  4 -2 -2  0  0  1
 0  0  0  0  1 -1  0  0  0  0 -1  1  0  0  0  0 

También he intentado encontrar un ejemplo con una proporción mejor que 7/2, manteniendo la simetría y un rectángulo de 1x4 en el centro, pero no he podido encontrar ninguno (el tamaño más grande que puedo comprobar es 33x38).

Answer 2

El límite superior es <3,95.

Espero que el código siguiente se muestre correctamente...

Demuestra que suponiendo una suma >=3,95 en el rectángulo central AxB de la cuadrícula ({-B,-B+A,-2A,-A,0,A,2A,B-A,B}+{0,A}) x ({-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,B}) conduce a una contradicción en un número finito de pasos. 3,95 no es el mejor posible para esta cuadrícula, pero 3,94 no conduce a una contradicción. Será fácil afinar el número, pero probablemente merezca más la pena buscar una rejilla más grande (lo que empieza a ser lento en awk.)

awk 'BEGIN {

 A=1;
 # pick B large enough to ensure that there
 # are no accidental squares in the grid below
 B=1000;

 # setting up the grid
 x[0]=-B;       x[1]=-B+A;
 x[1]=-B+A;     x[2]=-B+2*A;
 x[3]=-2*A;     x[4]=-A;
 x[4]=-A;       x[5]=0;
 x[5]=0;        x[6]=A;
 x[6]=A;        x[7]=2*A;
 x[7]=2*A;      x[8]=3*A;
 x[9]=B-A;     x[10]=B;
 x[10]=B;       x[11]=B+A;
 M=11;

 y[0]=-2*B;     y[2]=-B;
 y[1]=-B-A;     y[5]=-A;
 y[2]=-B;       y[6]=0;
 y[3]=-B+A;     y[7]=A;
 y[4]=-2*A;     y[9]=B-2*A;
 y[5]=-A;       y[10]=B-A;
 y[6]=0;        y[11]=B;
 y[7]=A;        y[12]=B+A;
 y[8]=2*A;      y[13]=B+2*A;
 y[10]=B-A;     y[14]=B+B-A;
 y[11]=B;       y[15]=B+B;
 y[12]=B+A;     y[16]=B+B+A;
 y[15]=2*B;     y[17]=3*B;
 N=17;

 for(i=0; i<=M; i++)
     for(j=i; j<=M; j++)
         for(k=0; k<=N; k++)
             for(l=k; l<=N; l++)
                 # 0 sum for degenerate rectangles
                 if(i==j || k==l) {
                     lo[i,j,k,l]=0;
                     hi[i,j,k,l]=0;
                 }                   
                 # squares
                 else if(x[j]-x[i]==y[l]-y[k]) {
                     lo[i,j,k,l]=-1;
                     hi[i,j,k,l]=1;
                 }
                 # other rectangles
                 else {
                     lo[i,j,k,l]=-4;
                     hi[i,j,k,l]=4;
                 }

 # central rectangle: assume its sum is >=3.95
 lo[5,6,6,11]=3.95;

 iter=10000;
 active=1;
 while(iter-- && active) {
     active=0;

     # traverse all possible combinations of 1 rectangle split into 4
     for(i=0; i<M; i++)
         for(j=i+1; j<=M; j++)
             for(k=0; k<N; k++)
                 for(l=k+1; l<=N; l++)
                     for(m=i; m<j; m++)
                         for(n=k; n<l; n++) {
                             lo0=lo[i,j,k,l];
                             lo1=lo[i,m,k,n];
                             lo2=lo[m,j,k,n];
                             lo3=lo[i,m,n,l];
                             lo4=lo[m,j,n,l];
                             hi0=hi[i,j,k,l];
                             hi1=hi[i,m,k,n];
                             hi2=hi[m,j,k,n];
                             hi3=hi[i,m,n,l];
                             hi4=hi[m,j,n,l];

                             # 3rd argument in max() and min() funtions
                             # is for printing purposes only...
                             lo0=max(lo0, lo1+lo2+lo3+lo4, 0);
                             hi0=min(hi0, hi1+hi2+hi3+hi4, 0);
                             lo1=max(lo1, lo0-hi2-hi3-hi4, 1);
                             lo2=max(lo2, lo0-hi1-hi3-hi4, 2);
                             lo3=max(lo3, lo0-hi1-hi2-hi4, 3);
                             lo4=max(lo4, lo0-hi1-hi2-hi3, 4);
                             hi1=min(hi1, hi0-lo2-lo3-lo4, 1);
                             hi2=min(hi2, hi0-lo1-lo3-lo4, 2);
                             hi3=min(hi3, hi0-lo1-lo2-lo4, 3);
                             hi4=min(hi4, hi0-lo1-lo2-lo3, 4);

                             if(lo0>hi0 || lo1>hi1 || lo2>hi2 || lo3>hi3 || lo4>hi4) {
                                 print "CONTRADICTION AT", i,m,j,k,n,l;
                                 exit;
                             }

                             lo[i,j,k,l]=lo0;
                             lo[i,m,k,n]=lo1;
                             lo[m,j,k,n]=lo2;
                             lo[i,m,n,l]=lo3;
                             lo[m,j,n,l]=lo4;
                             hi[i,j,k,l]=hi0;
                             hi[i,m,k,n]=hi1;
                             hi[m,j,k,n]=hi2;
                             hi[i,m,n,l]=hi3;
                             hi[m,j,n,l]=hi4;
                         }
 }
 print "FINISHED OK";
}

function max(s,t, where) {

if(s<t) {
    print "lo=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}

function min(s,t, where) {

if(s>t) {
    print "hi=" t, "for", i,m,j,k,n,l, "(" where ")";
    active=1;
    s=t;
}
return(s);
}
'

Answer 3

Últimas cifras

FG ha publicado una solución para el rectángulo de 12x1 ...alcanzando 181/48 = 3.3.7708333...

Más resultados:
El rectángulo de 11x1 es 101/27 = 3,740740...
El rectángulo de 7x3 es 56/15 = 3,733333...
El rectángulo 7x2 es 67/18 = 3,722222...
El rectángulo de 8x1 es 26/7 = 3,714285...
El rectángulo de 6x1 es 85/23 = 3,695652...
El rectángulo de 7x1 es 11/3 = 3,666666...
El rectángulo de 5x1 es 25/7 = 3,571428...

He eliminado las soluciones específicas de esta respuesta, ya que han sido superadas por los resultados de FG.

Answer 4

Recuerdo haber leído sobre esto en el libro de Discrepancia Geométrica de Matousek. Otra forma de expresar tu afirmación es que si la discrepancia de los cuadrados es pequeña, entonces también lo es la de los rectángulos. Creo que la versión de mayor dimensión de expresar el vector característico de un ladrillo con vectores característicos de cubos sigue abierta. Aquí tienes un artículo reciente relacionado que puede ser interesante para encontrar el límite exacto para tu pregunta: http://www.maths.qmul.ac.uk/~walters/papers/rectangles-as-sum-of-squares.pdf

Answer 5

He aquí una rápida descripción de la formulación de programación lineal que he utilizado para calcular algunas configuraciones:

Dada una $m \times n$ rejilla $G$ se puede describir una configuración con un vector real $x \in \mathbb{R}^{mn}$ . Entonces, para cada cuadrado que presenta una intersección no vacía con $G$ se puede escribir un vector indicador $a_i \in \mathbb{R}^{mn}$ ( $i \in S$ ), cuyos componentes son iguales a $1$ si está en la plaza, y $0$ de lo contrario. Por último, se puede escribir $c \in \mathbb{R}^{mn}$ , el indicador del rectángulo cuya suma se quiere maximizar.

El programa lineal es entonces $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ Este tipo de programa puede resolverse de forma extremadamente eficiente hasta tamaños relativamente grandes $mn$ (Estoy utilizando el solucionador CPLEX de ILOG).

Tener en cuenta la simetría es sencillo: si se quieren varios componentes de $x$ para que sean iguales entre sí, sólo se mantiene uno de ellos y se adaptan los restantes coeficientes en $c$ y $a_i$ (es decir, sustituirlos por la suma de los coeficientes correspondientes).

Sin embargo, este enfoque tiene limitaciones porque hay muchos vectores $a_i$ y esos vectores tienen a veces muchos componentes distintos de cero (lo que influye en la eficiencia del solucionador y, sobre todo, en la memoria utilizada). Sólo he podido utilizarlo hasta alrededor de un $45\times 45$ de la rejilla.

Para obtener soluciones para tamaños mayores, he utilizado el siguiente truco: en lugar de definir la variable $x_{ij}$ para el contenido del $(i,j)$ en la cuadrícula, defino la variable $y_{i,j}$ como sigue $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Entonces se puede comprobar que la suma del cuadrado o rectángulo con ángulos opuestos $(a,b)$ y $(c,d)$ es igual a $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$ . Esto significa que cada restricción del programa lineal correspondiente tendrá como máximo $4$ nonzeros, lo que mejora mucho la velocidad y los requisitos de memoria del solucionador.

Por cierto, voy a poner mis últimos resultados en el enlace http://dl.dropbox.com/u/217239/sol_rectangle.html

La mayor solución actual ( $56/15$ para un $3\times 7$ rectángulo), está hecho de fracciones con denominador común 120, pero esto es sólo una feliz coincidencia, ya que nada obliga a ello en el programa lineal (y, como comentó TonyK, hacerlo cumplir explícitamente sería muy costoso).

Actualización He realizado un amplio conjunto de ejecuciones para tamaños de rectángulo inferiores a 20x20 y he puesto los resultados al final del archivo enlazado anteriormente. El registro sigue siendo $56/15$ que es alcanzado por muchos rectángulos (especialmente por el $1 \times 9$ en un $101\times 109$ de la rejilla). Parece que se necesitarán cuadrículas aún más grandes para obtener sumas mayores.

Actualización2 $1 \times 11$ en un $137 \times 63$ la rejilla da $101/27$ = 3.7407407

Actualización3 $1 \times 12$ en un $155 \times 68$ la rejilla da $15/4$ = 3.75

Lamentablemente, sólo puedo comprobar $1 \times 13$ hasta alrededor de $191\times 77$ , que sigue dando 3,75, y parece que he agotado mis trucos por el momento...