This is an Opt In Archive . We would like to hear from you if you want your posts included. For the contact address see About this archive. All posts are copyright (c).
- Contents - Hide Contents - Home - Section 2Previous Next Last
1000 1050 1100 1150 1200 1250 1300 1350 1400 1450 1500 1550 1600 1650 1700 1750 1800 1850 1900 1950
1950 - 1975 -
Message: 1975 - Contents - Hide Contents Date: Wed, 14 Nov 2001 20:07:14 Subject: Re: Temperament bases and lattice basis reduction From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: > >> Nothing found. >> If you are very adventerous, of if by some chance you are on a Linux > box, you could try the freeware mathematicians have cooked up--Pari > and Lydia both have lattice basis reduction. Alas, they come from a > Unix/academic environment, and getting them up and running on a PC is > a pain.Unfortunately I don't understand what the point of this is. Could you please explain your original post to me?
Message: 1976 - Contents - Hide Contents Date: Wed, 14 Nov 2001 04:11:17 Subject: 8 note block from my example From: genewardsmith@xxxx.xxx I looked at the 8-note block from the LLL reduction of the 72-et I gave as an example, and got the following: 1-11/10-6/5-55/42-10/7-84/55-5/3-10/11-(2) Since I started from the 72-et, it seems reasonable to look at what this is in that system, which turns out to be the 10 9 9 9 7 9 9 10 pattern of steps. The block itself may be defined as (126/125)^round(14n/8) * (50/49)^round(11n/8) * (99/98)^round(4n/8) * (245/242)^n * (55/54)^round(12n/8) Here "round" rounds to the nearest integer, and n runs from -3 to 4.
Message: 1977 - Contents - Hide Contents Date: Thu, 15 Nov 2001 19:31:47 Subject: Re: Temperament bases and lattice basis reduction From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> Unfortunately I don't understand what the point of this is. Could > you>> please explain your original post to me? >> Let's first see if we have the idea of lattice basis reduction. I > randomly picked 225/224, 1029/1024 and 1728/1715 from a list of 7- > limit commas. The lattice they generate is > (225/224)^a (1029/1024)^b (1728/1715)^c, which as it happens is the > kernel of the 31-et in the 7-limit. However, there might be > a "better" basis for the kernel, in the sense that the Euclidean > lengths of these, considered as vectors, and the dot products of the > corresponding unit vectors, are smaller. In other words, we > take "better" to mean smaller vectors, more nearly orthogonal. The > idea of lattice basis reduction is to find a "better" basis.Aha! So this is related (as I suspected from its name) to the quest for "canonical unison vectors" for PBs that I asked you about a while back. However, I wouldn't compute lengths on a Cartesian or rectangular grid, which it seems you're doing here . . .> If I apply the LLL algorithm to the basis [-5,2,2,-1], [-10,1,0,3], > and [6,3,-1,-3] I get [1,2,-2,1], or 126/125; [-4,4,-1,0], or 81/80, > and [-1,-5,-1,4], or 2401/2430. If we check the Euclidean length and > the dot products for these, we find that they are, indeed, "better". > Moreover, they still generate the kernel of the 31-et. Considered as > commas for a block, they would give a 31-note block, but one with > more regularly sized steps. Also, they are larger. > > Does this make sense so far?Yup! Can we modify the algorithm so that it is uses lengths _not_ based on a Cartesian or rectangular grid? For example, if we used Kees van Prooijen's lattice, we might end up with the set of unison vectors that uses the smallest numbers in their ratios, for example.
Message: 1978 - Contents - Hide Contents Date: Thu, 15 Nov 2001 03:45:37 Subject: Re: Temperament bases and lattice basis reduction From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> Unfortunately I don't understand what the point of this is. Could you > please explain your original post to me?Let's first see if we have the idea of lattice basis reduction. I randomly picked 225/224, 1029/1024 and 1728/1715 from a list of 7- limit commas. The lattice they generate is (225/224)^a (1029/1024)^b (1728/1715)^c, which as it happens is the kernel of the 31-et in the 7-limit. However, there might be a "better" basis for the kernel, in the sense that the Euclidean lengths of these, considered as vectors, and the dot products of the corresponding unit vectors, are smaller. In other words, we take "better" to mean smaller vectors, more nearly orthogonal. The idea of lattice basis reduction is to find a "better" basis. If I apply the LLL algorithm to the basis [-5,2,2,-1], [-10,1,0,3], and [6,3,-1,-3] I get [1,2,-2,1], or 126/125; [-4,4,-1,0], or 81/80, and [-1,-5,-1,4], or 2401/2430. If we check the Euclidean length and the dot products for these, we find that they are, indeed, "better". Moreover, they still generate the kernel of the 31-et. Considered as commas for a block, they would give a 31-note block, but one with more regularly sized steps. Also, they are larger. Does this make sense so far?
Message: 1979 - Contents - Hide Contents Date: Thu, 15 Nov 2001 20:19:43 Subject: Re: Temperament bases and lattice basis reduction From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> Aha! So this is related (as I suspected from its name) to the quest > for "canonical unison vectors" for PBs that I asked you about a while > back.I think I mentioned lattice basis reduction then; I thought I'd try it. However, I wouldn't compute lengths on a Cartesian or> rectangular grid, which it seems you're doing here . . .That's the way the classic LLL, which is what I have on Maple, works. It's easy enough to adjust it somewhat, however, by adding multipliers, so that we could weight 3 and 5 more than 17 and 19, which might be a good plan.> Yup! Can we modify the algorithm so that it is uses lengths _not_ > based on a Cartesian or rectangular grid? For example, if we used > Kees van Prooijen's lattice, we might end up with the set of unison > vectors that uses the smallest numbers in their ratios, for example.I don't know what the van Prooijen lattice is; however, there *are* versions of LLL which work for noneuclidean metrics. I don't know if they've been implimented or how to lay hands on one, but I could try if this is what you mean.
Message: 1980 - Contents - Hide Contents Date: Thu, 15 Nov 2001 05:14:50 Subject: Another example From: genewardsmith@xxxx.xxx Let's start from the 441-et in the 11-limit. If I reduce the 5x6 matrix whose first row is [441,1,0,0,0,0] (telling me 2 is 441 steps in the 441-et) and last is [1526,0,0,0,1] (telling me 11 is 1526 steps in the 441-et) I will get vectors which span the same lattice, but which should be smaller and closer to being orthogonal. If the right hand column has smaller entries, that means they will have only a few steps in the 441-et, and hence will be small intervals. However, since I started from the 11-limit, these small intervals will still span the entire 11-limit, just as 2,3,5,7,11 do. When I do this, I do in fact get small intervals: 440/441, -1 steps; 539/540, -1 steps; 176/175, 4 steps; 1372/1375, -2 steps, and 11979/12005 0 steps--a 441 comma. If I leave off the column on the right, counting 441-et steps, I get a square matrix which must be unimodular--have determinant +-1, since it spans the 11-limit. I therefore may invert it, getting a matrix [-h49,h12,h72,-h58,-h31] of vals, which together with my intervals gives me a notation. I now may remove some of these vals, and see what lattice the remaining ones generate. They will span the dual group to the corresponding basis elements. If I eliminate h72 and -h31, I get something dual to <440/441, 539/540, 1372/1375>. If I apply lattice basis reduction to these, I don't get anywhere, since they are already reduced. However, I can reduce the dual lattice of vals, getting reduced vals. When I do this, I get [1 0 0] [1 -1 -3] [2 0 1] [0 -2 -1] [0 -2 1] These span the same group, dual to <440/441, 539/540, 1372/1375> as the 49, 12, and 58-et 11-limit vals. We now want to find the elements, corresponding to <440/441, 539/540, 1372/1375>, dual to these. They will give us a temperament with the same kernel elements, 176/175 and 12005/11979 in the 11-limit, and thus an 11-limit planar temperament. Since the vals have been reduced, however, we don't have so many generator steps to get to the primes, meaning these will be good choices for generators--or at least, better certainly than 441/440 and so forth! The top three rows of the above matrix gives us a 3x3 unimodular matrix, inverting it gives us [ 1 0 0] [ 7 -1 -3] [-2 0 1] The rows of this correspond to 2, 128/375, and 5/4, which we can use as approximations to the generators we seek. The full matrix above tells us how 2,3,5,7 and 11 are to be approximated using these three generators, each row representing a prime. We can replace 128/375 with 375/256 if we like, putting all the generators in an octave; if c~5/4 and d~375/256 the 5x3 matrix, after adjustment, tells us that 3 ~ 2^2 c^(-3) d 5 ~ 2^2 c 7 ~ 2^2 c^(-1) d^2 11 ~ 2^2 c d This defines the temperament; we can use least squares or linear programming to optimize and get tuning values for c and d. A quick check shows that this system is practical, though the 5 is a little sharp at 5.6 cents or thereabouts. This example was worked more or less at random, so there are plenty more of the same out there. Of course we can regard this as basically the 11-limit version of the 126/125 temperament.
Message: 1981 - Contents - Hide Contents Date: Thu, 15 Nov 2001 20:56:01 Subject: Re: Temperament bases and lattice basis reduction From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> Aha! So this is related (as I suspected from its name) to the quest >> for "canonical unison vectors" for PBs that I asked you about a > while >> back. >> I think I mentioned lattice basis reduction then; I thought I'd try > it. Awesome. > > However, I wouldn't compute lengths on a Cartesian or>> rectangular grid, which it seems you're doing here . . . >> That's the way the classic LLL, which is what I have on Maple, works. > It's easy enough to adjust it somewhat, however, by adding > multipliers, so that we could weight 3 and 5 more than 17 and 19, > which might be a good plan.Is 2 considered a prime on equal footing with the others?> > I don't know what the van Prooijen lattice is; however, there *are* > versions of LLL which work for noneuclidean metrics. I don't know if > they've been implimented or how to lay hands on one, but I could try > if this is what you mean.Well, Euclidean is not so bad to start with -- what I'm thinking is more triangular vs. rectangular, along the lines of the "15:8 should be a longer distance than 6:5" kind of thing . . .
Message: 1982 - Contents - Hide Contents Date: Thu, 15 Nov 2001 11:17:37 Subject: 19-limit planar temperament example From: genewardsmith@xxxx.xxx I thought I'd work a more elaborate example, to see if any problems arose--one did, but one easily dealt with. I started from the 8539-et in the 19-limit, to put the method to a more difficult test. Doing the lattice reduction and inverting gives a basis <10830/10829,50578/50575,28900/28899,12376/12375, 314721/314678,5928/5929,14364/14365,4914/4913>. On the grounds they were the three largest, I kept the 5th, 6th and 8th commas, and did a lattice reduction on the corresponding vals, which were the 581,742 and 954 ets. This gave me the following matrix: [-3 -3 2] [ 1 -5 -4] [-3 -2 2] [-1 1 7] [ 2 -4 1] [-2 -6 -1] [ 7 -6 -1] [ 4 0 8] I ran into difficulties with my trick of finding an invertible submatrix, but this is not really necessary. I simply fitted to the three generators (in a rough and ready way, using just the primes, which could be improved on in an example intended for use) and obtained generators of size 51.6, -859.188, 611.382; of course the negative cents can be replaced by positive cents and everything taken inside an octave. This resulted in a planar temperament all of whose 19-limit prime approximations were within a fraction of a cent (1/17 or less) of being just.
Message: 1983 - Contents - Hide Contents Date: Fri, 16 Nov 2001 05:39:16 Subject: Re: Temperament bases and lattice basis reduction From: Paul Erlich I wrote,> > Well, Euclidean is not so bad to start with -- what I'm thinking is > more triangular vs. rectangular, along the lines of the "15:8 should > be a longer distance than 6:5" kind of thing . . .Hmm . . . the point of this is to have simpler ratios span a smaller distance -- of course that's what the Tenney city-block metric, where the orientations of the axes don't matter, does so well. Can we develop a version of LLL for this metric? BTW, what's the optimality criterion used by the original LLL . . . that the sum of the lengths of the basis vectors be minimized, or what?
Message: 1984 - Contents - Hide Contents Date: Fri, 16 Nov 2001 06:48:04 Subject: Re: Temperament bases and lattice basis reduction From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> Hmm . . . the point of this is to have simpler ratios span a smaller > distance -- of course that's what the Tenney city-block metric, where > the orientations of the axes don't matter, does so well.I've not heard of a Tenney metric, but it sounds like you are talking about the L1 (taxicab) metric, for which there is an LLL variant, at least in theory--or so I've heard. Can we> develop a version of LLL for this metric? BTW, what's the optimality > criterion used by the original LLL . . . that the sum of the lengths > of the basis vectors be minimized, or what?The criterion somewhat complicated, but I could post it if you really need it, and want to hear about Gram-Schimdt and put up with the fact that there is a parameter involved, so there really isn't just one version anyway. The problem was that if you insist on a canonical optimally reduced basis, the problem is NP complete, but the trick is to relax the condition enough to get a polynomial time algorithm. It then turns out that most of the time, it gives you more than you've proven it ought to, anyway. It's been a real breakthrough in computational math.
Message: 1985 - Contents - Hide Contents Date: Fri, 16 Nov 2001 07:57:39 Subject: Re: Temperament bases and lattice basis reduction From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> Hmm . . . the point of this is to have simpler ratios span a > smaller>> distance -- of course that's what the Tenney city-block metric, > where>> the orientations of the axes don't matter, does so well. >> I've not heard of a Tenney metric,City-block metric, where the length of one rung along prime axis p is log(p).> but it sounds like you are talking > about the L1 (taxicab) metric,Yes, but with the above rung lengths.> for which there is an LLL variant, at > least in theory--or so I've heard. Cool. > Can we>> develop a version of LLL for this metric? BTW, what's the > optimality>> criterion used by the original LLL . . . that the sum of the > lengths>> of the basis vectors be minimized, or what? >> The criterion somewhat complicated, but I could post it if you really > need it, and want to hear about Gram-Schimdt and put up with the fact > that there is a parameter involved, so there really isn't just one > version anyway. The problem was that if you insist on a canonical > optimally reduced basis, the problem is NP complete, but the trick is > to relax the condition enough to get a polynomial time algorithm. It > then turns out that most of the time, it gives you more than you've > proven it ought to, anyway. It's been a real breakthrough in > computational math.Well then I'd like to understand the condition, and if it (for some or all choices of the parameter) has any relatively simple musical interpretation. Especially if you can hunt down the taxicab version.
Message: 1986 - Contents - Hide Contents Date: Sat, 17 Nov 2001 03:09:33 Subject: Re: Harmonic entropy From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> For harmonic entropy, each "state" is a just dyad (or n-ad in future > versions), i.e., a ratio. The universe of possible ratios is > determined by a rule (such as max(p,q)<N or p*q<N, generally any rule > such that p(j)*q(i) - p(i)*q(j) = 1 for any pair of adjacent ratios p > (i)/q(i), p(j)/q(j), and with N tending toward infinity). The > probability of each dyad is determined by determining the > corresponding area under a normal curve (whose s.d. is an input > parameter) standard, centered around the actual input value.The "actual input value" is a certain number of cents, so how can a normal curve be centered around it? The> width of the "slice" corresponding to each dyad is determined > assuming that it occupies the full "range" between the adjacent > mediants.A "dyad" is a fraction reduced to lowest terms, e.g 5/4, if I am following you. The "adjacent mediants" is not clear, but perhaps you mean the fractions on each side of the Farey sequence in which the "dyad" first appears? In the case of 5/4, that would be 1/1 < 5/4 < 4/3, so we would integrate a normal function between 1 and 4/3 to get p?
Message: 1987 - Contents - Hide Contents Date: Sun, 18 Nov 2001 02:14:55 Subject: Re: Harmonic entropy From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:>> The >> probability of each dyad is determined by determining the >> corresponding area under a normal curve (whose s.d. is an input >> parameter) standard, centered around the actual input value. >> The "actual input value" is a certain number of cents, Right. > so how can a > normal curve be centered around it?If the number of cents is c, the curve is y=1/(s*sqrt(2*pi))*exp((x-c)^2/2*s^2) where x is the position on the interval axis (have you looked at any of the harmonic entropy curves)?>> The >> width of the "slice" corresponding to each dyad is determined >> assuming that it occupies the full "range" between the adjacent >> mediants. >> A "dyad" is a fraction reduced to lowest terms, e.g 5/4, if I am > following you. Yes. > The "adjacent mediants" is not clear, but perhaps you > mean the fractions on each side of the Farey sequence in which > the "dyad" first appears?No, I mean the mediants between the fraction and its immediate neighbors in a Farey sequence of order N.> In the case of 5/4, that would be > 1/1 < 5/4 < 4/3, so we would integrate a normal function between 1 > and 4/3 to get p?You would integrate between two complicated ratios, typically both very close to 5/4, but far closer to 5/4's immediate successor and immediate predecessor in the Farey sequence of order N (because N is large). Thus 5/4 would typically end up with a much greater probability than its neighbors.
Message: 1988 - Contents - Hide Contents Date: Sun, 18 Nov 2001 02:17:34 Subject: LLL basis for ETs From: Paul Erlich It would be great to see the LLL bases for all the "good" ETs in each limit. This should use the log(p) weighting, and, if possible, the taxicab metric. Also, I'd like to understand the parameter you mentioned and the optimization criterion too.
Message: 1989 - Contents - Hide Contents Date: Sun, 18 Nov 2001 10:09:39 Subject: Re: LLL definitions From: Graham Breed Paul wrote:> Well that kind of slams the door on the "classification" I was hoping > to acheive, though I suppose a classification by optimal generators > would be good enough (and would eliminate the need to use LLL, but I > feel we should still have some lower bound on > allowable "orthogonality").The mapping by period and generator is unique for any linear temperament, which should be relevant here. Some caveats: There are always two choices of generator within the period. I used to always take the smaller, but sometimes it became the larger after optimization. So you can make the arbitrary choice that the first nonzero term be negative. For similar reasons, there may be more than one period mapping. I think we can do without it, and take the raw generator mapping, including a common factor showing the number of periods to the octave. If you're going to do that, you have to get rid of torsion. I expect any decent LLL algorithm will do this. Going from unison vectors to linear temperaments is a done deal. I have a fresh installation of Mandrake 8.1 here, which comes with Numeric Python as standard! So, all I need to do is make a local copy of my website and I can look into these things. It also comes with Octave. Is that supposed to do LLL? Graham
Message: 1990 - Contents - Hide Contents Date: Sun, 18 Nov 2001 02:33:30 Subject: Re: LLL basis for linear temperaments From: Paul Erlich Gene, it looks, from your post on the tuning list, that a basis need not be complete for LLL to be performed on it. So can you perform LLL on the list of, say, 7-limit linear temperaments represented by any pair of commatic unison vectors from the list: 49:50 63:64 80:81 125:126 225:224 245:243 1024:1029 2400:2401 4374:4375 and (optionally, if the task is not to onerous) 1715:1728 3125:3136 4374:4375 I'd expect we'd end up with a relatively manageable list of distinct temperaments, for which the LLL basis will, if nothing else, serve as a label for each equivalence class of bases.
Message: 1991 - Contents - Hide Contents Date: Sun, 18 Nov 2001 10:05:38 Subject: Re: LLL basis for linear temperaments From: Graham Breed Gene:>> I had in mind a similar project, which was to go >> through pairs of ets in the 11-limit, and LLL reduce to linear >> temperaments. Sometimes there is more that one good way to do this; > I>> was thinking at least of posting the example of 12 and 34.Note that this project is what my temperament finder is trying to do. Thanks for the definition of LLL, Gene. I'll read it and see if I can implement it. So far that's the main weak point of the program.> Graham expressed some confusion as to what you were doing with pairs > of ETs and I share his confusion.The confusion was because he was coming up with unique results for inconsistent temperaments. Firstly, he's said that he takes the nearest prime approximations, which should clear up the confusion although I'm not sure our results agree. Secondly, this is exactly the problem he mentions in that paragraph! Graham
Message: 1992 - Contents - Hide Contents
Date: Sun, 18 Nov 2001 05:05:43
Subject: LLL definitions
From: genewardsmith@xxxx.xxx
We begin with a real n-dimensional vector space R^n with an inner
product, which we denote by <u, v>. In orthonormal coordinates this
will be the ordinary dot product; if we want another inner product
for LLL reduction one way to do it is to transform coordinates and
then transform them back.
The goal of lattice basis reduction is to obtain a lattice basis
equivalent to a given basis that consists of short vectors or, stated
another way, into a basis consisting of vectors that are pairwise
nearly orthogonal.
Starting from an ordered lattice basis [b_1, b_2, ..., b_m] we can
obtain another basis [g_1, g_2, ..., g_m] by the Gram-Schmidt
orthogonalization process. This will span the same linear subspace,
but *not*, normally, the same lattice. We also obtain Gram-Schmidt
coefficients:
c[i,j] = <b_i, g_j>/<g_j, g_j>
We do this by the standard Gram-Schmidt recursion from linear algebra:
g_1 = b_1
g_i = b_i - sum_{j = 1 to i - 1} c[i,j] g_j
Definition:
An ordered basis [b_1, b_2, ..., b_m] in R^n is called *size-reduced*
if |c[i,j]| <= 1/2 for 1 <= j < i <= m.
Definition:
An ordered basis [b_1, b_2, ..., b_m] in R^n is called
*LLL-reduced with constant d*, where d satisfies 1/4 < d < 1, if it
is size-reduced and if
d |g_{k-1}|^2 <= |g_k + c[k, k-1] g_{k-1}|^2 for k = 2, 3, ..., m.
The constant d is not documented in the sketchy Maple help file, but
chances are good it is 3/4, since this is what Lenstra, Lenstra and
Lovasz used originally and it is a sort of default standard. The
larger d is the better your chance of an optimal reduction, but for
such small problems as we are looking at I suspect we are getting
that anyway.
Message: 1993 - Contents - Hide Contents Date: Sun, 18 Nov 2001 05:15:37 Subject: Re: LLL basis for linear temperaments From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> I'd expect we'd end up with a relatively manageable list of distinct > temperaments, for which the LLL basis will, if nothing else, serve as > a label for each equivalence class of bases.That's a thought; I had in mind a similar project, which was to go through pairs of ets in the 11-limit, and LLL reduce to linear temperaments. Sometimes there is more that one good way to do this; I was thinking at least of posting the example of 12 and 34.
Message: 1994 - Contents - Hide Contents Date: Sun, 18 Nov 2001 05:25:42 Subject: Re: LLL definitions From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> We begin with a real n-dimensional vector space R^n with an inner > product, which we denote by <u, v>. In orthonormal coordinates this > will be the ordinary dot product; if we want another inner product > for LLL reduction one way to do it is to transform coordinates and > then transform them back.Is there a continuous, reversible transformation between Euclidean and taxicab?> > Starting from an ordered lattice basis [b_1, b_2, ..., b_m] we can > obtain another basis [g_1, g_2, ..., g_m] by the Gram-Schmidt > orthogonalization process. This will span the same linear subspace, > but *not*, normally, the same lattice.What do you mean by the "lattice" spanned by a particular basis, as opposed to the linear subspace spanned by a particular basis? Do you mean something that musically speaking, is or corresponds to the particular JI Fokker periodicity block (just a guess)?> We also obtain Gram-Schmidt > coefficients: > > c[i,j] = <b_i, g_j>/<g_j, g_j>OK . . .> We do this by the standard Gram-Schmidt recursion from linear algebra: > g_1 = b_1 > g_i = b_i - sum_{j = 1 to i - 1} c[i,j] g_jThis I'm familiar with.> Definition: > An ordered basis [b_1, b_2, ..., b_m] in R^n is called *size- reduced* > if |c[i,j]| <= 1/2 for 1 <= j < i <= m.I'm confused as to why you use b here rather than g. I thought b was the given basis, and g the derived one. Given a basis (but allowing changes that leave the linear subspace unchanged), does this size-reduced basis always exist? Is it always unique?> Definition: > An ordered basis [b_1, b_2, ..., b_m] in R^n is called > *LLL-reduced with constant d*, where d satisfies 1/4 < d < 1, if it > is size-reduced and if > > d |g_{k-1}|^2 <= |g_k + c[k, k-1] g_{k-1}|^2 for k = 2, 3, ..., m.Hmm . . . how is this motivated?> The constant d is not documented in the sketchy Maple help file, but > chances are good it is 3/4, since this is what Lenstra, Lenstra and > Lovasz used originally and it is a sort of default standard. The > larger d is the better your chance of an optimal reduction, but for > such small problems as we are looking at I suspect we are getting > that anyway.Hmm . . . do certain values of d guarantee existence, and/or do certain other values guarantee uniqueness?
Message: 1995 - Contents - Hide Contents Date: Sun, 18 Nov 2001 05:39:54 Subject: Re: LLL basis for linear temperaments From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> I'd expect we'd end up with a relatively manageable list of > distinct>> temperaments, for which the LLL basis will, if nothing else, serve > as>> a label for each equivalence class of bases. >> That's a thought;Is it? I think something of the sort, with pretty color graphics and lots of musical explanations, would make a great paper for XH18 (coming out in Februrary). Would you like to co-author such a paper with me, or perhaps write one paper upon which I'd draw in one of my own . . . ?> I had in mind a similar project, which was to go > through pairs of ets in the 11-limit, and LLL reduce to linear > temperaments. Sometimes there is more that one good way to do this; I > was thinking at least of posting the example of 12 and 34.Graham expressed some confusion as to what you were doing with pairs of ETs and I share his confusion. Perhaps we could attempt to begin directly from the list of unison vectors, drawing up a list of ETs and corresponding LLLs (where the "orthogonality" is above some threshold, if that makes any sense) that result from triplets of UVs, and a list of linear temperaments and their LLLs (where the "orthogonality" is above some threshold, if that makes still makes any sense) that result from pairs of UVs. Hopefully we can use the Tenney lattice, with a Euclidean metric if need be, or preferably a taxicab one. We will then be able to see certain cases where the result of combining two ETs is quite clear -- they'll unambiguously have two UVs in common.
Message: 1996 - Contents - Hide Contents Date: Sun, 18 Nov 2001 05:47:27 Subject: Re: LLL definitions From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> Is there a continuous, reversible transformation between Euclidean > and taxicab?In the finite-dimensional case, they define the same topology; hence the identity map is continuous.> What do you mean by the "lattice" spanned by a particular basis, as > opposed to the linear subspace spanned by a particular basis?The lattice consists of the Z-linear combinations of basis vectors; if they are [1, 2, 1] and [0, 1 0] then the lattice is [a, 2a + b, a] for any pair of integers a and b. The subspace consists of the R-linear combinations, so in this case a and b are any real numbers.>> Definition: >> An ordered basis [b_1, b_2, ..., b_m] in R^n is called *size- > reduced*>> if |c[i,j]| <= 1/2 for 1 <= j < i <= m.> I'm confused as to why you use b here rather than g. I thought b was > the given basis, and g the derived one.So it is, but it's b which is or isn't size reduced. We create g and c in order to find if b is size-reduced.> Given a basis (but allowing changes that leave the linear subspace > unchanged), does this size-reduced basis always exist? Is it always > unique?It exists, since we can show the LLL algorithm works, and that gives size-reduction plus more. It is not in general unique.> >> Definition:>> An ordered basis [b_1, b_2, ..., b_m] in R^n is called >> *LLL-reduced with constant d*, where d satisfies 1/4 < d < 1, if it >> is size-reduced and if >> >> d |g_{k-1}|^2 <= |g_k + c[k, k-1] g_{k-1}|^2 for k = 2, 3, ..., m.> Hmm . . . how is this motivated?I warned you this was ugly. Using this definition, we can prove theorems showing that the basis vectors of an LLL-reduced basis can't be too large, relatively speaking. We can also get a polynomial time algorithm which gives us such a reduced basis.> Hmm . . . do certain values of d guarantee existence, and/or do > certain other values guarantee uniqueness?We don't have uniqueness, though in practice for such small problems as we are looking at we very likely do get it. Existence we do have, since LLL will work for this range of d.
Message: 1997 - Contents - Hide Contents Date: Sun, 18 Nov 2001 05:59:58 Subject: Re: LLL basis for linear temperaments From: genewardsmith@xxxx.xxx --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote:> Is it? I think something of the sort, with pretty color graphics and > lots of musical explanations, would make a great paper for XH18 > (coming out in Februrary). Would you like to co-author such a paper > with me, or perhaps write one paper upon which I'd draw in one of my > own . . . ?I'm not likely to produce pretty color graphics on my own, and my experiences with attempted publication in non-mathematical forums suggest to me that I might need a coauthor. If you understood everything a paper said, and I thought nothing it said was wrong, that would be a great start. On the other hand there are probably lots of things we have discussed which could be the basis of such a project, so are you sure this is the right one to start out with? Presumably, we don't need to define LLL-reduction, but can cite a reference.
Message: 1998 - Contents - Hide Contents Date: Sun, 18 Nov 2001 06:06:04 Subject: Re: LLL definitions From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> Is there a continuous, reversible transformation between Euclidean >> and taxicab? >> In the finite-dimensional case, they define the same topology; hence > the identity map is continuous.So that's promising for being able to use the Tenney metric eventually, yes?>>> What do you mean by the "lattice" spanned by a particular basis, as >> opposed to the linear subspace spanned by a particular basis? >> The lattice consists of the Z-linear combinations of basis vectors; > if they are [1, 2, 1] and [0, 1 0] then the lattice is [a, 2a + b, a] > for any pair of integers a and b. The subspace consists of the > R-linear combinations, so in this case a and b are any real numbers.OK . . . somehow I has skipped over the whole orthogonalization step in my mind when I asked this question. Sorry! Now I'm confused>>> Definition: >>> An ordered basis [b_1, b_2, ..., b_m] in R^n is called *size- >> reduced*>>> if |c[i,j]| <= 1/2 for 1 <= j < i <= m. >>> I'm confused as to why you use b here rather than g. I thought b > was>> the given basis, and g the derived one. >> So it is, but it's b which is or isn't size reduced. We create g and > c in order to find if b is size-reduced.OK -- so you should have said "for all g" in the definition . . . yes? Or is g uniquely defined? It would seem to depend on how you order the elements of b, since the first vector is made to be the same.>>> Given a basis (but allowing changes that leave the linear subspace >> unchanged), does this size-reduced basis always exist? Is it always >> unique? >> It exists, since we can show the LLL algorithm works, and that gives > size-reduction plus more. It is not in general unique.Well that kind of slams the door on the "classification" I was hoping to acheive, though I suppose a classification by optimal generators would be good enough (and would eliminate the need to use LLL, but I feel we should still have some lower bound on allowable "orthogonality").>> Hmm . . . do certain values of d guarantee existence, and/or do >> certain other values guarantee uniqueness? >> We don't have uniqueness, though in practice for such small problems > as we are looking at we very likely do get it.Can we determine for certain whether we do or don't in any particular case?> Existence we do have, > since LLL will work for this range of d.I was thinking that two different choices of b might turn out to be equal contenders for the LLL throne for a particular equivalence class of b's. Possible or impossible?
Message: 1999 - Contents - Hide Contents Date: Sun, 18 Nov 2001 06:13:20 Subject: Re: LLL basis for linear temperaments From: Paul Erlich --- In tuning-math@y..., genewardsmith@j... wrote:> --- In tuning-math@y..., "Paul Erlich" <paul@s...> wrote: >>> Is it? I think something of the sort, with pretty color graphics > and>> lots of musical explanations, would make a great paper for XH18 >> (coming out in Februrary). Would you like to co-author such a paper >> with me, or perhaps write one paper upon which I'd draw in one of > my>> own . . . ? >> I'm not likely to produce pretty color graphics on my own,I've already produced some for a few linear temperaments . . . I thought I'd simply make more.> If you understood > everything a paper said, and I thought nothing it said was wrong, > that would be a great start. On the other hand there are probably > lots of things we have discussed which could be the basis of such a > project, so are you sure this is the right one to start out with?Virtually all of my discussions with you have been geared toward this one project -- start by motivating periodicity blocks, continue by motivating temperament of smaller unison vectors, and conclude by motivating ETs and linear temperaments. In the process one supplies a few spelled-out examples and a fairly comprehensive list of possibilities, the list obtained with as few conditions as one can manage.