[GAP Forum] Choosing random elements from a group

[Sandeep Murthy]

Thank you,

I'm working on a random search algorithm for
basic finite non-Abelian groups initially of
order <= 10^12.

At what point does the randomness of PseudoRandom()
degrade compared to Random() for this situation?

Specifically, I need to find a triple of subsets
S,T,U of sizes say m, p, q resp. in a non-Abelian finite
group G of order say n such that the following
size conditions are satisfied:

1. n <= mpq < = floor(n^(1.5)) - the triple product of
  the subset sizes is at least the group order and
less than 1.5 times the group order.

2. floor(n^(1.5)) - mpq is a minimum over all
subset triples satisfying a certain simple algebraic
condition.

Sincerely, Sandeep.

P. S. I note that the GAP manual describes a RandomList()
method that is said to be effective for dense lists up
2^28 long.



On 19 May 2009, at 05:14, Alexander Hulpke wrote:

> Dear Forum, Dear Sandeep Murthy,
>
>>
>> I'd like to know the best way to choose random elements
>> of a group in GAP?
>
> That depends on your choice of group (Is it finite? Permutations?  
> Presentation? Matrices?), your criteria for randomness, and  
> (definition of ``best'') your preferences for memory use and runtime.
>
> Two default functions are
> Random
> which tries to create an equal distribution (subject to the  
> randomness of the built-in random number generator, of course), but  
> requires the ability to enumerate all elements of the group (I.e. it  
> does not work for infinite groups and -- for example -- very badly  
> for large matrix groups or finitely presented groups) and
> PseudoRandom
> which uses only generators and limited memory/run time, but does not  
> guarantee true randomness.
>
> Best,
>
>   Alexander Hulpke
>
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
> http://www.math.colostate.edu/~hulpke
>
>