Gene's Generator Generator

A generator generator is a thing that generates generators, of course!

I spend some time looking at Gene's generator-finding algorithm, which
he sent offlist. My conclusion is that we're basically doing the same
thing with very minor differences. Gene's approach is as follows:

Assume we want to find the generator corresponding to the ith val of a
non-contorted mapping matrix M. Then, if monzos are rows:

1) Find the null space of M, call it N. Make sure that this is an
integer matrix.
2) Find an arbitrary generator with rational coefficients by taking
the ith monzo of the pseudoinverse of M.
3) Tack it onto the null space as the top row.
4) Clear denominators in this top row.
5) Saturate the resulting matrix.
6) For each row in the matrix, figure out what it maps to under the
ith val, and append this as an additional augmented coordinate to the
left of the row.
7) Put this in Hermite form. Note the top row will now have augmented
coordinate 1 and not-so-coincidentally be the generator, and the other
rows will have aug coordinate 0 and not-so-coincidentally also be in
the null space.
8) Lop off the augmented coordinates, take the top generator monzo,
feed it and the bottom null space monzos in rational form into Gene's
mystery "redic" function, which somehow reduces it in a better way
than my Hermite form thing.

The key thing here is that it doesn't matter what order you do steps
4, 5, and 6 in. If you were instead to insert step 6 before step 4,
then Gene's procedure would lead to you immediately appending an
augmented coordinate of 1 to the row corresponding to the
pseudoinverse entry, and an augmented coordinate of 0 to the rows
corresponding to the null space. Clearing denominators and saturating
after the fact would then still give you the same result, but make it
more explicit that you're performing elementary row operations on an
augmented matrix.

The augmented monzo matrix is central to both of these algorithms.
Gene constructs the augmented monzo matrix manually by getting an
arbitrary rational generator via the pseudoinverse, combining it with
the null space matrix, and then attaching the augmented coordinates.
My way takes the null space of the augmented *mapping* matrix
directly, which gives you the augmented monzo matrix in one step. Both
algorithms then go on to clear denominators, saturate, reduce to some
normal form, etc.

The only thing I don't get is in Gene's mystery "redic" function from
step #8, which reduces things much better than any of these variations
on Hermite form. Gene asked me what the best way was to find the
lowest-complexity generator from my approach, so my answer is "take it
and send it into your redic function."

Which means I need to ask Gene, what's the idea behind your redic
procedure? Is it guaranteed to actually give you the lowest-Tenney
height result? (I see it keeps calling your "redi" procedure, which
partially reduces it, until it arrives at a stable result.)

-Mike

On Sat, Jun 2, 2012 at 4:53 AM, Mike Battaglia <battaglia01@gmail.com> wrote:
>
> The augmented monzo matrix is central to both of these algorithms.
> Gene constructs the augmented monzo matrix manually by getting an
> arbitrary rational generator via the pseudoinverse, combining it with
> the null space matrix, and then attaching the augmented coordinates.

One thing I also still don't get is why the whole affine space thing
works out so naturally. I guess there's something magical about
identifying (x, y, z) with ax + by + cz = 1, emphasis on the 1...

-Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> Gene asked me what the best way was to find the
> lowest-complexity generator from my approach, so my answer is "take it
> and send it into your redic function."

My redic function blows. I've long thought I should take a look at improving it.

On Sun, Jun 3, 2012 at 5:00 PM, genewardsmith <genewardsmith@sbcglobal.net>
wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...>
> wrote:
>
> > Gene asked me what the best way was to find the
> > lowest-complexity generator from my approach, so my answer is "take it
> > and send it into your redic function."
>
> My redic function blows. I've long thought I should take a look at
> improving it.

OK, somewhere in the affine subspace lies the interval with the lowest
complexity also lying in Z^n, which I'll call C. Also in this subspace
lies the pseudoinverse P, which lies in Q^n. Seems like there ought to
be an upper bound on the weighted distance d between P and C, yes?
Then you could just look at all the points in the d-neighborhood of P
which are also in Z^n, of which there will be a finite amount, and
pick the one with lowest compexity.

-Mike

On Sun, Jun 3, 2012 at 5:47 PM, Mike Battaglia <battaglia01@gmail.com> wrote:
>
> OK, somewhere in the affine subspace lies the interval with the lowest
> complexity also lying in Z^n, which I'll call C. Also in this subspace
> lies the pseudoinverse P, which lies in Q^n.

I dunno if this terminology is right if you're using weighted
coordinates, but whatever. Just take the weighted coordinate version
of what I said.

-Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

> OK, somewhere in the affine subspace lies the interval with the lowest
> complexity also lying in Z^n, which I'll call C. Also in this subspace
> lies the pseudoinverse P, which lies in Q^n. Seems like there ought to
> be an upper bound on the weighted distance d between P and C, yes?
> Then you could just look at all the points in the d-neighborhood of P
> which are also in Z^n, of which there will be a finite amount, and
> pick the one with lowest compexity.

I think it might help to find a Graver basis routine, especially if I could get one in Maple; don't know if there is one.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:

> I think it might help to find a Graver basis routine, especially if I could get one in Maple; don't know if there is one.

So far this is the best I can find. I am not a happy camper.

http://www.4ti2.de/

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
>
>
>
> --- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@> wrote:
>
> > I think it might help to find a Graver basis routine, especially if I could get one in Maple; don't know if there is one.
>
> So far this is the best I can find. I am not a happy camper.
>
> http://www.4ti2.de/
>

Brute force might do it, especially if I can figure out how to bound the search. This is the Wikipedia definition of a Graver basis:

http://en.wikipedia.org/wiki/Graver_basis#Formal_definition

We can cut that in half, since a Graver comma basis could consist only of elements greater than 1, and we allow multiplication and division. What I got for a Graver basis for the commas of 11-limit miracle was {225/224, 1029/1024, 2401/2400, 16875/16807, 33075/32768, 823543/819200, 1063125/1048576, 34171875/33554432}. The idea is that you reduce using commas in the Graver basis one comma at a time. If it works as it's supposed to, and finding the Graver basis isn't too hard, that should be a good way of improving "redic".

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
What I got for a Graver basis for the commas of 11-limit miracle was {225/224, 1029/1024, 2401/2400, 16875/16807, 33075/32768, 823543/819200, 1063125/1048576, 34171875/33554432}.

Bah. I think I screwed up again.

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
>
>
>
> --- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@> wrote:
> What I got for a Graver basis for the commas of 11-limit miracle was {225/224, 1029/1024, 2401/2400, 16875/16807, 33075/32768, 823543/819200, 1063125/1048576, 34171875/33554432}.
>
> Bah. I think I screwed up again.
>

Let's try septimal meantone as an example: 81/80, 126/125, 225/224, 3136/3125, 3645/3584, 5103/5000, 59049/57344, 321489/312500, 20253807/19531250, 1275989841/1220703125. The question is, how do I find this expeditiously?