Fwd: [GAP Forum] Choosing random elements from a group

[Sandeep Murthy]

I forgot to mention that my starting point is
a subset triple (S=G,T=1,U=1) - where 1 is the trivial
subgroup of G - which we know satisfies
the algebraic condition - and then randomly
subtract elements from G, add elements to
T and to U such that the resulting product size
satisfies the size conditions.

Sincerely, Sandeep.

Begin forwarded message:

> From: Sandeep Murthy <srmurthy at brookes.ac.uk>
> Date: 19 May 2009 05:41:40 BST
> To: GAP forum <forum at gap-system.org>
> Cc: Alexander Hulpke <hulpke at me.com>
> Subject: Re: [GAP Forum] Choosing random elements from a group
>
> 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
>>
>>
>
>

Sandeep Murthy
Ph. D. Student
Computing & Mathematical Sciences
Room C.202C
School of Technology
Oxford Brookes University
Wheatley, Oxfordshire OX33 1HX
United Kingdom

Ph: (01865) 485605