|
|
A181566
|
|
Minimum number of random elements such that their orders allow identification of an abelian group of order n (sampled uniformly) with probability greater than 1/2.
|
|
0
|
|
|
0, 0, 0, 2, 0, 0, 0, 4, 3, 0, 0, 3, 0, 0, 0, 8, 0, 3, 0, 4, 0, 0, 0, 7, 5, 0, 8, 5, 0, 0, 0, 16, 0, 0, 0, 9, 0, 0, 0, 12, 0, 0, 0, 5, 4, 0, 0, 19, 7, 5, 0, 6, 0, 12, 0, 16, 0, 0, 0, 6, 0, 0, 5, 37, 0, 0, 0, 6, 0, 0, 0, 20, 0, 0, 5, 6, 0, 0, 0, 32, 27, 0, 0, 6, 0, 0, 0, 26, 0, 5, 0, 7, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
LINKS
|
|
|
EXAMPLE
|
For n=4, by the fundamental theorem of finite abelian groups, the group is either Z4 or Z2 x Z2. When you choose 2 random elements, if 1 element comes out of the 2 elements of order 4, you will know you have Z4. If the 2 elements are of order 2 in Z2 x Z2, you will know you have Z2 x Z2. Calculating the probabilities, when you choose 2 random elements, if the group is Z4, there is a 5/6 chance of knowing it. If it is Z2 x Z2, there is a 1/2 chance of knowing it. Since we assume each non-isomorphic abelian group of order n has the same probability of being the group, averaging 5/6 and 1/2 we get a 2/3 chance that the group is known after choosing 2 elements. Since the probability that a single random element will allow us to identify the group is 1/4, which is not greater than 1/2, a(4) = 2.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Edited and terms a(16) onward added by Max Alekseyev, Oct 07 2023
|
|
STATUS
|
approved
|
|
|
|