Block-circulant can be used in two senses: that the blocks are circulant, or that the template in which the blocks are placed is circulant. Your formula requires both senses! In general, there are formulas for determinants of a block matrix in terms of polynomial expressions in the blocks provided that the blocks commute.

In the integers, Golomb rulers coincide with (a special case of) Sidon sets, but the generalisation to an arbitrary group is straighforward. Often Golomb rulers crop up in discussions about sequences with small autocorrelation (for applications in communications). If I remember rightly Golomb was motivated by optimal placements of receivers for a signal from a satellite.

Yes - I had $\mathbb{C}$ in mind, I should have been more careful!

At least in coprime characteristic, you're asking for permutation groups which have rank 2: these are precisely the 2-transitive groups. These are classified, for example in "Permutation Groups" by Dixon and Mortimer. An infinite family of solvable examples are the groups $AGL_{1}(q)$, and a theorem of Burnside shows that any solvable example has prime power degree.

Let $H_2 = 2^{-1/2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$, then the group generated with $S_{2}$ is finite, as is the group generated by $H_4 = H_2 \otimes H_2$ with $S_{4}$, I think. Computing minimal polynomials of a few random products $H_{16}PH_{16}$ shows that many of these matrices have infinite order, though.

@Trunk I think that's an uncharitable interpretation of what I've written. These mathematicians were working before the development of modern techniques (and in fact the modern techniques were developed in part to refine their results and place them on a solid foundation). They were sophisticated mathematical thinkers with superb intuition for finding interesting and fundamental results. Their mathematical language was inadequate to describe what they perceived in some cases, and their intended audience could be expected to fill in an generalise arguments in others.

@TimothyChow I think the second proposal is closer to the truth. In the examples I've given Sylvester and Cayley are aware that they've proved the smallest interesting case of a general phenomenon. They consider it clear that the pattern they observed will generalise, and make this claim. I presume they would have tested further cases before writing. But, in my reading, they know that their proof is not complete.

Yes! David's answer is wonderful, and I feel I learned something useful from it, but this is the way to get what I want computationally. Thank you both!

I agree this is a weird set of demands, but in fact I think this is pretty close to my situation, actually. In any case, I'd like to see how it is done!

Yes! It is now clear to me that this is necessary and sufficient. Is it possible to describe the other roots explicitly as polynomials in $\alpha_{1}$ under these assumptions? (Which of course is what I should have asked in the first place.)

@ArnoFehm Yes, for irreducible polynomials it is necessary that the Galois group be regular. But it is not clear to me that this is sufficient. The group need not be cyclic: the cyclotomic polynomials show that more-or-less arbitrary abelian Galois groups can occur for irreducible polynomials with this property. But the question holds also for general polynomials; $x^{n} - 1$ will have the property, for example.

Apologies for any imprecision - let us take $p(x)$ as fixed. The question is then under what conditions a root of $p(x)$ and its powers form a $\mathbb{Q}$-generating set for the splitting field.