Cayley Table Sudoku

Given an $$n\times n$$ grid partially filled with the numbers $$0,\ldots, n-1$$, we can play a Sudoku-like game by trying to fill in the rest of the grid so that the end result is the Cayley table for a group (edit: where position $$i,j$$ in the table would represent the product of $$i$$ and $$j$$ in the group structure).

I am curious about the following value: let $$g(n)$$ represent the smallest natural number such that if $$g(n)$$ squares in an $$n\times n$$ grid are filled, then the configuration always can be extended to a solution in at most $$1$$ way.

Another way to think of this question is as follows: How similar can two distinct $$n\times n$$ Cayley tables be? $$g(n)$$ is the smallest natural number such that if two $$n\times n$$ Cayley tables agree for $$g(n)$$ entries, then they are identical.

What does $$g(n)$$ look like? I'm most interested in the asymptotic behaviour (as I imagine $$g(n)$$ may fluctuate wildly as $$n$$ increases due to the fluctuation in the number of groups of order $$n$$ as $$n$$ increases). One particularly interesting question: can $$g(n)\over n^2$$ be bounded above by a constant (say, 0.99)? In other words, if two Cayley tables agree on $$99\%$$ of entries, must they be identical? And if so, how much lower than $$0.99$$ can we bring this constant?

• If you are asking for equality of tables (as opposed to isomorphism), probably not. For Latin Squares, take an $n\times n$ and swap the $1$s and $2$s entries. That changes $2n$ entries, and $(n^2-2n)/n^2\to 1$ as $n\to\infty$. But that leads to equivalent Latin Squares. You should probably be asking for equivalent Cayley tables or isomorphic groups, rather than identical tables. Feb 16 at 15:37
• @ArturoMagidin I see what you are saying. I was imagining that the entry in position $i,j$ of the table would represent the product of $i$ and $j$, hence permutations of the rows/columns wouldn't be an issue, though I realize the way I wrote it left that open. I made an edit, hopefully that cleared it up. Feb 16 at 19:33
• This function is indeed fluctuating wildly. If $n$ happens to be a prime, there is exactly one group of that order, so even a completely empty Cayley table determines the group uniquely. For a few cases like $n=p^2$ or $n=p^3$ one can probably explicitly compute $g(n)$. For $n$ a power of $2$ gives the largest number of non-isomorphic groups and probably the biggest overlap in Cayley tables of different groups. Feb 17 at 19:59

1 Answer

As a partial answer to your second question: in 1992 Ales Drápal proved that if two finite groups agree on 89% on their multiplication tables, the groups must be isomorphic! He conjectured that the same holds true if the tables agree on 75% of their entries. I do not think the conjecture has been proved yet. See also Groups St. Andrews 2001 at Oxford, featuring the paper in Vol. 1, p. 143, of Drápal On the distance of 2-groups and 3-groups.

See also A. Drápal, How far apart can the group multiplication tables be?, European J. Combin. 13 (1992), no. 5, 335–343.

• See my earlier MSE question: math.stackexchange.com/q/4810756 The upper and lower bounds are already improved to 83.3% and 77.8% respectively. Feb 18 at 6:02