Construction of \((k+1)\)-orbits of permutation groups from their \(k\)- orbits (Q1311126)

Let \(G\) be a permutation group on a set \(X\) of finite cardinality \(n\). The author considers the question: can two permutation groups on \(X\) have the same \(k\)-orbits (that is, orbits on the set of unordered \(k\)-subsets of \(X\)) but distinct \((k+1)\)-orbits? A \(k\)-orbit \(h\) is restorable if there is no other \(k\)-orbit \(h'\) such that for any \(c\in h\) and \(c'\in h'\) and any \((k-1)\)-orbit \(f\), \(c\) and \(c'\) have the same number of \((k- 1)\)-element subsets lying in \(f\). The restorability index of \((G,X)\) is the unique positive integer \(\rho(G)\), such that not all \(\rho(G)\)-orbits are restorable, but for every \(k>\rho(G)\) all \(k\)-orbits are restorable (and \(\rho(G)\) is defined to be 1 if \(G\) has a unique \(k\)-orbit for each \(k\leq n\)). In earlier work, the author showed that \(\rho(G)\leq\min\{n/2,1+\log_ 2| G|\}\). Here, it is shown that if \(k\geq\rho(G)\) then the \(k\)- orbits of \(G\) uniquely determine the \((k+1)\)-orbits. This has a neat algebraic proof, giving an algorithm for finding the \((k+1)\)-orbits. It follows as an easy corollary that all orbits of \(G\) can be recovered from its \(\rho(G)\)-orbits.