4
$\begingroup$

Let $G$ be a group of order $n$, on elements $x_1, ..., x_n$.

Let's draw the Cayley table of the group, that is, table $A$ with $a_{i,j}$ = [number of $x_i \circ x_j$ in the list $x_1, ..., x_n$] After that, if we erase $K$ entries of the table, for some $K$ it's always possible to determine the deleted entries, and for some $K$ it's not possible since there exist some group $G'$ (maybe, isomorphic to $G$ and maybe not) whose Cayley table is different from $A$, but only in some of the erased cells.

The question is, whether it's always possible to determine original table (for all sufficiently large $n$) if $K=2n$.

Here's what I know so far:

if $K=4n-4$, the table can't be reconstructed when we delete 2 rows and 2 columns, corresponding to identity and some other element $x$ (so, after that we won't be able to determine the difference between them, and different tables for the same group count as different)

if $K=n$, it's possible for $n \neq 4$, because

  • if some column contains only one empty cell, we know what was written in that cell, since all elements in any column must be different

  • after that, you have at least $\lceil \frac{n}{2} \rceil$ columns in which you know every single entry

  • Subset of $G$, corresponding to such columns, form a subgroup of $G$, since if you know $x\circ y$ for any $x$, and $x\circ z$ for any $x$ in $G$, then you know $x \circ y \circ z$ for any $x$ in $G$, and $y^{-1}=y^{n-1}$. Let's denote that subgroup $H$.

  • So if you know more than $\frac{n}{2}$ columns, you can reconstruct the table, and the only case when you can't is when $n$ is even and in exactly $\frac{n}{2}$ columns exactly two entries are unknown.

  • The set of elements corresponding to not-yet-known columns is a coset of $H$ ($H$ is subgroup of index 2). That is, its elements are of the form $gh$, $h \in H$, where $g$ is fixed. To know what is $gh_i \circ gh_j$, it's sufficient to know which element equals $gh_i g$ (since we know how to multiply by elements of $H$). And to determine $gh_ig$ we look at cells corresponding to $gh_i \circ gh_j$ (they are in the same column) For all $j$ (except maybe two) we know the value of $g h_i g h_j$ and so, if $n>4$, we definitely know what is $gh_i g$.

  • The same for $h_i \circ gh_j$

So, I'm asking about $K=2n$. Those tricks with subgroup of index two won't work, but I don't think that there are counterexamples for arbitrarily large $n$.

Sorry for my English and unnecessary longishness of description. Feel free to edit the question.

$\endgroup$
  • $\begingroup$ I think the question of the minimum number of entries that can be deleted to prevent the table from being reconstructed is very interesting. On the other hand, I don't think your statement that deleting two rows and columns (including the identity) is sufficient is correct. Take for example an elementary abelian 2-group of order $n\geq 16$. All the entries on the diagonal are identical and I think no other group of order $n$ has at least $n-2$ elements squaring to a given element. So you can certainly recognise the identity. $\endgroup$ – verret Mar 29 '16 at 3:00
  • $\begingroup$ Even the cyclic group of order $3$ is a counterexample. If you write a single entry on the diagonal but not on the identity row (which is what would be left after your deletion), I can recover the rest of the table: the fact that the diagonal entry is not equal to the row index tells me that this is not the identity row, and the diagonal entry must be the square element and the remaining element is the identity. For example, if I have a group of order 3 with ground set $\{a,b,c\}$ and $a^2=b$, then $c$ is the identity and $a$ and $b$ are inverses of each other. $\endgroup$ – verret Mar 29 '16 at 3:00
  • $\begingroup$ In general, I think you need to delete a lot more entries than this, maybe even a positive fraction. This is not exactly the same, but see the following for example: mathoverflow.net/questions/204218/… math.uzh.ch/fileadmin/user/rosen/publikation/zu08p.pdf $\endgroup$ – verret Mar 29 '16 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.