[GAP Forum] Running through subspaces over finite field

[Rudolf Zlabinger]

Dear Arturo Magidin,

if I understood right, you want to handle a collection:

gap> v:=GF(3)^10;
( GF(3)^10 )
gap> subspaces:=Subspaces(v,8);
Subspaces( ( GF(3)^10 ), 8 )
gap> IsCollection(subspaces);
true
gap>

For collections that are not lists, the default method is IteratorList(
Enumerator( C ) ).  (Reference Manual.... Iterators)

Normally you would use enum:=Enumerator(subspaces), and then set enum[xxx] 
to your desired element, but Enumerator(subspaces) runs out of time and out 
of storage. Whereas you can process an Enumerator in the same way as a list, 
an Iterator only is usable step by step, therefore the definition of an 
Iterator is unsignificant to time and storage independent from the magnitude 
of the collection.

The problem now is, that Enumerator doesnt run for the magnitude of your 
collection, and an Iterator cannot be preset to a predefined element.

The best I see, is, that an Iterator remembers the last element called by 
NextIterator, so you can remember different states by different variables, 
you have to use ShallowCopy to get a different Object::

gap> iterrat:=Iterator(Rationals);
<iterator>
gap> NextIterator(iterrat);
0
gap> NextIterator(iterrat);
1
gap> NextIterator(iterrat);
-1
gap> NextIterator(iterrat);
1/2
gap> iterrat0010:=ShallowCopy(iterrat);
<iterator>
gap> NextIterator(iterrat);
2
gap> NextIterator(iterrat);
-1/2
gap> NextIterator(iterrat);
-2
gap> NextIterator(iterrat0010);
2
gap>

Maybe, and I hope so, you get better messages,

all the best, Rudolf





----- Original Message ----- 
From: "Arturo Magidin" <magidin at member.ams.org>
To: "GAP Forum" <Forum at gap-system.org>
Sent: Monday, June 11, 2007 9:27 PM
Subject: [GAP Forum] Running through subspaces over finite field


> Dear Forum,
>
> I'm doing some experiments in which I am looking at subspaces over a
> finite field of p elements. I am sure I will have more questions later,
> but I wanted to start with a (hopefully) simple one.
>
> For the past several days I've been running the tests over the subspaces
> of dimension 8 of the space of dimension 10 over GF(3) (there are about 74
> million such subspaces).
>
> After defining
>
> gap> V:=GF(3)^10;
> gap> subspaces:=Subspaces(V,8);
>
> I defined an iterator,
>
> gap> iter:=Iterator(subspaces);
>
>
> I am producing a list of subspaces that have the property I want, by
> having a counter that I increase whenever I apply NextIterator to iter,
> and then printing the number.
>
> My question is whether there is an easy way to acces the nth subspace
> produced by the iterator other than to iterate it a step at a time.
>
> For example, when p=3, the first subspace I find with the property I want
> is the 6591-st one. I want to look more closely at this subspace (e.g.,
> its basis, etc).  In this case, since it is a pretty small number, I can
> do a loop to advance the iterator to the position and thus obtain a
> pointer that points to the desired subspaces. So I can do:
>
> gap>  for i in [1..6590] do
>    >    xx:=NextIterator(iter);
>    >  od;
>
> and so I end up with xx being the subspace I want to look at.
>
> Is there some better way? Is there some way to move the iterator directly
> a certain number of positions?
>
> After several days, for example, I know that the 5,428,815-st subspace
> checked has the property.  Advancing the iterator that much with a loop as
> above would take a non-negligible amount of time.
>
> Or, I am running a similar experiment with p=5; here, I know none of the
> first 100,000 subspaces have the property, but even just running the
> iterator forward 100,000 times takes a non-negligible amount of time. So I
> would like to be able to simply move the iterator or a pointer to "the
> 100,001-st subspace" and start from there. Or check some small ranges for
> other primes (say, from the 1,000,000-th subspace to the 1,100,000-th). Or
> maybe even random subspaces.
>
> So, the question in summary is: is there some way to access the n-th
> subspace in
>
>    Subspaces(V,k)
>
> without using an iterator, or some way of advancing the iterator a given
> number of steps directly?
>
> Thanks in advance,
>
> Arturo Magidin
> magidin at member.ams.org
>
>
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>