¿Qué tan cerca se puede llegar a los planos proyectivos finitos que faltan?

Question

Esta pregunta puede ser interpretado como una instancia de la Zarankiewicz problema. Supongamos que tenemos una $n\times n$ matriz con entradas en $\{0,1\}$ con el no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ menor. El problema pide el máximo número posible de entradas igual a $1$. Al $n=q^2+q+1$, uno puede tomar la incidencia de la matriz de (puntos frente líneas) de lo finito plano proyectivo de orden $q$, dando la respuesta $(q^2+q+1)(q+1)$. Además se puede demostrar que esta respuesta es óptima, cuando un plano proyectivo de orden existe. Ya que no hay finito plano proyectivo de orden $6$ uno se puede preguntar

¿Cuál es el máximo número posible de entradas igual a $1$ en un $43\times 43$ de la matriz?

El límite superior de $(6^2+6+1)(6+1)=301$ no puede ser alcanzado, pero es la respuesta cerca de ella?

La motivación aquí es entender si proyectiva aviones son "mal approximable" cuando no existe para un determinado fin. Uno puede especular que la respuesta a la pregunta anterior está dado por el corte de un plano proyectivo de orden $7$ un selecto conjunto de $13$ puntos y líneas, pero no estoy seguro.

Answer 1

Me funksionin GAP

 MaxOnes := n -> Maximum(List(Filtered(AsList(GF(2)^[n,n]),
                             M->not ForAny(Tuples([1..n-1],2),
                                           s->ForAny(Cartesian([1..n-s[1]],[1..n-s[2]]),
                                                     t->ForAll(Flat(M{[s[1],s[1]+t[1]]}
                                                                     {[s[2],s[2]+t[2]]}),
                                                               IsOne)))),
                             N->Number(Flat(N),IsOne)));
 

ne kemi per shembull

 gap> MaxOnes(1);
1
gap> MaxOnes(2);
3
gap> MaxOnes(3);
6
gap> MaxOnes(4);
9
 

dhe pergjigja e pyetjes eshte

 gap> MaxOnes(43);
( ... ju lutem prisni ... ju lutem prisni ... !! )