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 <[email protected]>
Date: 19 May 2009 05:41:40 BST
To: GAP forum <[email protected]>
Cc: Alexander Hulpke <[email protected]>
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: [email protected], 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
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
