Yahoo Tuning Groups Ultimate Backup tuning-math Very relevant paper, and the question I'm currently thinking about

http://dx.doi.org/10.1145/347476.347482

You can interpret this paper as being about MOSes and MOS generalization from a "melodic" perspective (perfectly even arrangement of steps).

Check out Theorem 2.20. Very familiar, right?

Also, here's a question I'm currently trying to answer:

Given a word over a d-letter alphabet (i.e. rank-d scale imprint), consider the d-dimensional lattice set consisting of the frequency tuples of all prefixes of that word. For example, aabacababc maps to {(0,0,0),(1,0,0),(2,0,0),(2,1,0),(3,1,0),(3,1,1),(4,1,1),(4,2,1),(5,2,1),(5,3,1),(5,3,2)}. Is the property that this lattice set is convex equivalent to a simple property of the original word, for example, one related to balance?

For a 2-letter alphabet the answer is simple: the only periodic words that correspond to convex lattice sets are MOSes, which can also be described in terms of balance, in terms of the floor function, in terms of Euclid's algorithm, etc.

But for 3-letter and larger alphabets, how do you just look at a word and tell whether it corresponds to a convex lattice set?

Keenan

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@> wrote:
> >
> > On Thu, Oct 13, 2011 at 3:55 PM, Keenan Pepper <keenanpepper@> wrote:
> > >
> > > I don't know about that, because it's publicly accessible. But I'll definitely send it to you in an email if you want.
> >
> > Doesn't look publicly accessible over here; I see a link to "Buy this
> > Article" but no free full text link.
>
> Sorry; I meant that the files section of the tuning-math group is publicly accessible, not that the paper is.

But now I feel stupid, because it's clearly not, even if you have a link. I wonder why I thought that?

Anyway, since the files section is in fact *not* publicly accessible, I guess I'll upload a copy.

Keenan

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "keenan_pepper" <keenanpepper@...> wrote:
> But for 3-letter and larger alphabets, how do you just look at a word and tell whether it corresponds to a convex lattice set?

Theorem: Every convex scale with three incommensurate step sizes has max variety <= 4.

Someone, Carl I believe, made a similar claim earlier and now I've proved it to my satisfaction (and could write out a formal proof if necessary). My reasoning goes like this:

* Every scale with three incommensurate step sizes is epimorphic under the val expressed as < 1 1 1 | in the basis of steps.

* Every convex epimorphic scale is a centrally symmetric hexagon, because along with the degenerate case of parallelograms, that's the only convex polygon that tiles the plane.

* Every centrally symmetric hexagon has a "difference body" that is a 2x scaled copy of the same hexagon, and furthermore it divides up into regions that are equivalent to four copies of the original hexagon, cut up and jumbled around (I'll provide a diagram of this later). Therefore, every such hexagon has max variety <= 4.

So, max variety <= 4 is a necessary condition for convexity in such scales. I conjecture that it is also sufficient:

Conjecture: Every scale with three incommensurate step sizes and max variety <= 4 is convex.

Any counterexamples?

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>Theorem: Every convex scale with three incommensurate step sizes has
>max variety <= 4.
>Someone, Carl I believe, made a similar claim earlier and now I've
>proved it to my satisfaction (and could write out a formal proof if
>necessary). My reasoning goes like this:

Yup, that was me. I based it on parallelograms and linear
combinations, but I missed FFBs (which I still need to look at).
Are all FFBs "centrally symmetric" hexagons?

>Conjecture: Every scale with three incommensurate step sizes and max
>variety <= 4 is convex.

Without stating bounds on approximations and valid subgroups,
this doesn't seem very strong. (?)

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
>
> Keenan wrote:
>
> >Theorem: Every convex scale with three incommensurate step sizes has
> >max variety <= 4.
> >Someone, Carl I believe, made a similar claim earlier and now I've
> >proved it to my satisfaction (and could write out a formal proof if
> >necessary). My reasoning goes like this:
>
> Yup, that was me. I based it on parallelograms and linear
> combinations, but I missed FFBs (which I still need to look at).
> Are all FFBs "centrally symmetric" hexagons?

Yes. By "centrally symmetric hexagon" I mean a hexagon with three pairs of parallel edges. Could also be called "inversion symmetric". A parallelogram is a limiting case of a centrally symmetric hexagon with two very short edges.

> >Conjecture: Every scale with three incommensurate step sizes and max
> >variety <= 4 is convex.
>
> Without stating bounds on approximations and valid subgroups,
> this doesn't seem very strong. (?)

Everything I'm talking about is totally mapping-agnostic, so I don't know what you mean by "subgroups" here.

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>parallelogram is a limiting case of a centrally symmetric hexagon with
>two very short edges.

Yes, I caught that.

>> >Conjecture: Every scale with three incommensurate step sizes and max
>> >variety <= 4 is convex.
>>
>> Without stating bounds on approximations and valid subgroups,
>> this doesn't seem very strong. (?)
>
>Everything I'm talking about is totally mapping-agnostic, so I don't
>know what you mean by "subgroups" here.

What kind of "convexity" are you talking about, if not that of
approximate just intonation?

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> >Everything I'm talking about is totally mapping-agnostic, so I don't
> >know what you mean by "subgroups" here.
>
> What kind of "convexity" are you talking about, if not that of
> approximate just intonation?

Simply the general idea of convexity on a lattice; specifically the lattice generated by the steps.

In the JI major scale, my steps are log(9/8), log(10/9), and log(16/15), which are provably incommensurate (fundamental theorem of arithmetic). The lattice they generate is the 5-limit JI lattice (you can tell because their monzos form a unimodular matrix), so convexity on this lattice is the ordinary JI convexity you're used to.

But nothing's stopping me from making a scale with (logarithmic) step sizes 1, 1/pi, and 1/pi^2, which are also incommensurate (because pi is transcendental). These steps also generate a lattice, and it makes just as much sense to talk about convex sets on this lattice. It's just that this lattice has nothing to do with JI.

So whatever weird JI subgroup I'm working in doesn't matter, because the convexity property makes no reference to JI mappings at all.

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>> What kind of "convexity" are you talking about, if not that of
>> approximate just intonation?
>
>Simply the general idea of convexity on a lattice; specifically the
>lattice generated by the steps.

Oh, the lattice generated by the steps. Given epimorphicity, I
suppose such a lattice is transformable to JI... given a mapping
("approximation bounds").

>But nothing's stopping me from making a scale with (logarithmic) step
>sizes 1, 1/pi, and 1/pi^2, which are also incommensurate (because pi
>is transcendental). These steps also generate a lattice, and it makes
>just as much sense to talk about convex sets on this lattice.

It most certainly does not.

>So whatever weird JI subgroup I'm working in doesn't matter, because
>the convexity property makes no reference to JI mappings at all.

Are we venturing into music-theoretic masturbation now?

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> >Simply the general idea of convexity on a lattice; specifically the
> >lattice generated by the steps.
>
> Oh, the lattice generated by the steps. Given epimorphicity, I
> suppose such a lattice is transformable to JI... given a mapping

Yes, of course. It is simply the change of basis given by the unimodular matrix formed by the monzos of the steps.

> ("approximation bounds").

No idea what this means here.

> >But nothing's stopping me from making a scale with (logarithmic) step
> >sizes 1, 1/pi, and 1/pi^2, which are also incommensurate (because pi
> >is transcendental). These steps also generate a lattice, and it makes
> >just as much sense to talk about convex sets on this lattice.
>
> It most certainly does not.

Do you want me to give a formal definition of a convex lattice set?

A lattice is a Z-module.

A convex combination of elements {a1,a2,...} of a Z-module is defined as another element b such that there exist nonnegative integers c1,c2,... such that

(c1 + c2 + ...) b = c1 a1 + c2 a2 + ...

A convex set in a Z-module is defined as a subset S of that Z-module such that every convex combination of elements of S is contained in S.

Clearly this definition makes sense no matter what the basis elements of the Z-module are. They could be log(2), log(3), log(5)... as in JI, or they could be other incommensurate numbers, or more abstract vectors.

> >So whatever weird JI subgroup I'm working in doesn't matter, because
> >the convexity property makes no reference to JI mappings at all.
>
> Are we venturing into music-theoretic masturbation now?

No.

Keenan

🔗Carl Lumma <carl@lumma.org>

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:
>
> > ("approximation bounds").
>
> No idea what this means here.

It's a reference to my previous.

> > >These steps also generate a lattice, and it makes
> > >just as much sense to talk about convex sets on this lattice.
> >
> > It most certainly does not.
>
> Do you want me to give a formal definition of a convex lattice set?

I was referring to the "just as much sense" part, which it
absolutely, unequivocally does not make.

> > Are we venturing into music-theoretic masturbation now?
>
> No.

Sure sounds like it to me!

-Carl

🔗Mike Battaglia <battaglia01@gmail.com>

On Oct 14, 2011, at 9:21 PM, "Carl Lumma" <carl@lumma.org> wrote:

> > Are we venturing into music-theoretic masturbation now?
>
> No.

Sure sounds like it to me!*
*

You're misunderstanding Keenan's remarks. The point isn't that pi and e have
as much psychoacoustic significance as 3/2 and 5/4, it's that the
mathematical property of "convexity" can be defined over both lattices, and
hence isn't tied to any particular basis or subgroup or to JI at all.

It's not "masturbation" because it solves the problem you originally brought
up, which is to define "convexity" in a way that's affine-invariant and
invariant with respect to any basis or subgroup you choose. Luckily, the
convexity of a set is already defined in an affine-invariant way, and that's
what it is.

-Mike

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
> You're misunderstanding Keenan's remarks. The point isn't that pi and e have
> as much psychoacoustic significance as 3/2 and 5/4, it's that the
> mathematical property of "convexity" can be defined over both lattices, and
> hence isn't tied to any particular basis or subgroup or to JI at all.
>
> It's not "masturbation" because it solves the problem you originally brought
> up, which is to define "convexity" in a way that's affine-invariant and
> invariant with respect to any basis or subgroup you choose. Luckily, the
> convexity of a set is already defined in an affine-invariant way, and that's
> what it is.

Yeah, that's all I meant - that the property of convexity doesn't depend on mappings or JI subgroups because it has nothing to do with JI at all.

I would never propose actually making music in a temperament based on pi, because that's retarded (with apologies to Charles Lucy).

Keenan

🔗Carl Lumma <carl@lumma.org>

🔗Mike Battaglia <battaglia01@gmail.com>

On Sat, Oct 15, 2011 at 2:59 AM, Carl Lumma <carl@lumma.org> wrote:
>
> Mike wrote:
>
> >It's not "masturbation" because it solves the problem you originally brought up, which is to define "convexity" in a way that's affine-invariant and invariant with respect to any basis or subgroup you choose.
>
> It's obvious that scales of restricted variety will be convex
> if we can force any val onto them.

What do you mean by "force any val onto them?"

> Wouldn't it make more sense to reserve calling things "convex" that are convex in
> a space that matters (that is, with suitable "approximation
> bounds") and are hence rare?

I don't know what you mean by "approximation bounds," but in general,
no, it wouldn't make more sense to do things that way, for the same
reason that I chose to define MODMOS's in terms of unmapped generators
and an L-s chroma instead of periodicity blocks and a unison vector.

-Mike

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> It's obvious that scales of restricted variety will be convex
> if we can force any val onto them. That's why I said it doesn't
> seem very strong -- it's just a definition. Wouldn't it make
> more sense to reserve calling things "convex" that are convex in
> a space that matters (that is, with suitable "approximation
> bounds") and are hence rare?

Are you saying that the statement I'm interested in is obviously true?

If so, would you mind supplying a proof?

Just to be clear, the statement is:

For every word W on the alphabet {a,b,c} which has max variety <= 4, the set of ordered triples of the counts of a, b, and c in each prefix of W is a convex lattice set in Z^3.

(I would need to give a definition of "max variety" but I assume you know what that means already.)

Also, if the truth of this statement is indeed obvious, then perhaps it has a simple generalization to words on an n-letter alphabet in Z^n. Care to give the function f(n) for the max variety needed?

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>For every word W on the alphabet {a,b,c} which has max variety <= 4,
>the set of ordered triples of the counts of a, b, and c in each prefix
>of W is a convex lattice set in Z^3.

You'll have to say what an "ordered triple of the counts in
a word prefix" is.

For convexity, I expect that every shortest lattice path between
two points in the scale will contain only other points in the
scale. There is a question of what to do when two or more paths
are tied for shortest. I'm inclined to allow any one of these
to work. What do you think?

It looks like convexity depends on the lattice group. For
instance, 1/1 6/5 5/4 is convex in A2 but not Z2. Now, it is
also not connected in Z2, and it looks like any scale that is
connected in both and convex in one is convex in the other.
Counterexamples?

What I think is obvious is that every scale that periodically
covers an n-dimensional lattice must be transformable by n
coprime commas to convex scale with a convex convex hull defined
by those commas. And that any such scale has max variety = 2^n.
At least for 1 < n < 4.

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
>
> Keenan wrote:
>
> >For every word W on the alphabet {a,b,c} which has max variety <= 4,
> >the set of ordered triples of the counts of a, b, and c in each prefix
> >of W is a convex lattice set in Z^3.
>
> You'll have to say what an "ordered triple of the counts in
> a word prefix" is.

The prefixes of "word" are "w", "wo", "wor", and "word". You know, prefixes.

The count of a symbol is the number of times it occurs, so by "ordered triple of counts" I mean an ordered triple of integers where the first is the numer of 'a's, second is the number of 'b's, third is the number of 'c's.

> For convexity, I expect that every shortest lattice path between
> two points in the scale will contain only other points in the
> scale. There is a question of what to do when two or more paths
> are tied for shortest. I'm inclined to allow any one of these
> to work. What do you think?

What definition of "lattice path" do you have in mind here? Does a point have a finite number of neighbors, or infinitely many?

If the edges of a "lattice path" can only be steps, then there exist convex lattice sets that are not path-connected, for example {(0,0,0),(1,1,1)}. This is a convex lattice set according to the definition I gave, but non connected by this kind of path.

On the other hand, if the edges of a "lattice path" can be arbitrary line segments between lattice points, then every shortest path in a convex lattice set does belong to the set, but now this is not a sufficient condition for convexity. {(0,0,0),(1,2,0),(2,1,0)} contains all its shortest paths, but is not convex since (1,1,0) is in its convex hull.

> It looks like convexity depends on the lattice group. For
> instance, 1/1 6/5 5/4 is convex in A2 but not Z2. Now, it is
> also not connected in Z2, and it looks like any scale that is
> connected in both and convex in one is convex in the other.
> Counterexamples?

What is "A2"?

> What I think is obvious is that every scale that periodically
> covers an n-dimensional lattice must be transformable by n
> coprime commas to convex scale with a convex convex hull defined
> by those commas. And that any such scale has max variety = 2^n.
> At least for 1 < n < 4.

What does "transformable by [commas]" mean? If it means what I think it does, then yeah, this is pretty trivial.

Keenan

🔗Carl Lumma <carl@lumma.org>

>> >For every word W on the alphabet {a,b,c} which has max variety <= 4,
>> >the set of ordered triples of the counts of a, b, and c in each prefix
>> >of W is a convex lattice set in Z^3.
>>
>> You'll have to say what an "ordered triple of the counts in
>> a word prefix" is.
>
>The prefixes of "word" are "w", "wo", "wor", and "word". You know, prefixes.

Is "ord" a prefix? It seems odd to exclude it.

>> For convexity, I expect that every shortest lattice path between
>> two points in the scale will contain only other points in the
>> scale. There is a question of what to do when two or more paths
>> are tied for shortest. I'm inclined to allow any one of these
>> to work. What do you think?
>
>What definition of "lattice path" do you have in mind here?

http://en.wikipedia.org/wiki/Taxicab_distance

>Does a point have a finite number of neighbors, or infinitely many?

Finite.

>If the edges of a "lattice path" can only be steps, then there exist
>convex lattice sets that are not path-connected, for example
>{(0,0,0),(1,1,1)}. This is a convex lattice set according to the
>definition I gave,

Where did you give a definition of convexity?

>but non connected by this kind of path.

Right, and since it's not connected it can't be convex by the
definition I gave.

>On the other hand, if the edges of a "lattice path" can be arbitrary
>line segments between lattice points, then every shortest path in a
>convex lattice set does belong to the set, but now this is not a
>sufficient condition for convexity. {(0,0,0),(1,2,0),(2,1,0)} contains
>all its shortest paths, but is not convex since (1,1,0) is in its
>convex hull.

Huh? There are several length-3 paths from (2 1 0) or (1 2 0)
to the origin, passing either through (1 1 0), (2 0 0) or (0 2 0);
none of these three points are in the set.

>> It looks like convexity depends on the lattice group. For
>> instance, 1/1 6/5 5/4 is convex in A2 but not Z2. Now, it is
>> also not connected in Z2, and it looks like any scale that is
>> connected in both and convex in one is convex in the other.
>> Counterexamples?
>
>What is "A2"?

The triangular lattice.

>> What I think is obvious is that every scale that periodically
>> covers an n-dimensional lattice must be transformable by n
>> coprime commas to convex scale with a convex convex hull defined
>> by those commas. And that any such scale has max variety = 2^n.
>> At least for 1 < n < 4.
>
>What does "transformable by [commas]" mean? If it means what I think
>it does, then yeah, this is pretty trivial.

It's what you think (multiplication by a linear combination of
the commas).

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> >The prefixes of "word" are "w", "wo", "wor", and "word". You know, prefixes.
>
> Is "ord" a prefix? It seems odd to exclude it.

A prefix is something that appears at the *beginning* of a word. If I had meant to include "ord" I would have said something like "substring". I meant prefix.

> >If the edges of a "lattice path" can only be steps, then there exist
> >convex lattice sets that are not path-connected, for example
> >{(0,0,0),(1,1,1)}. This is a convex lattice set according to the
> >definition I gave,
>
> Where did you give a definition of convexity?

Definition of "convex lattice set":

/tuning-math/message/19781

> >but non connected by this kind of path.
>
> Right, and since it's not connected it can't be convex by the
> definition I gave.

Where did *you* give a definition?

If your definition is different from mine you should give it a different name, because mine is the standard definition of "convex lattice set" among mathematicians who study discrete geometry. For example, http://books.google.com/books?id=WehCspo0Qa0C&pg=PA422 and http://books.google.com/books?id=MHVBQ2J7-9AC&pg=PA87 "Intersection of a convex body with the lattice" is equivalent to my definition, and I can prove it.

> >On the other hand, if the edges of a "lattice path" can be arbitrary
> >line segments between lattice points, then every shortest path in a
> >convex lattice set does belong to the set, but now this is not a
> >sufficient condition for convexity. {(0,0,0),(1,2,0),(2,1,0)} contains
> >all its shortest paths, but is not convex since (1,1,0) is in its
> >convex hull.
>
> Huh? There are several length-3 paths from (2 1 0) or (1 2 0)
> to the origin, passing either through (1 1 0), (2 0 0) or (0 2 0);
> none of these three points are in the set.

Read the first sentence of the paragraph you're responding to. (Or just ignore this part because it wasn't what you meant by "lattice path".)

> >What is "A2"?
>
> The triangular lattice.

I don't understand. Given that a lattice is defined as a Z-module, how is this lattice different from Z2? They seem to be the same lattice.

> >What does "transformable by [commas]" mean? If it means what I think
> >it does, then yeah, this is pretty trivial.
>
> It's what you think (multiplication by a linear combination of
> the commas).

I assume you mean multiplication of each element by a linear combination of commas, which are possibly all different. But then this transformation can map any scale that's epimorphic (under the val you get from tempering out all the commas) to any other scale epimorphic under that val, so yeah, it's trivially true.

Keenan

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>> Is "ord" a prefix? It seems odd to exclude it.
>
>A prefix is something that appears at the *beginning* of a word. If I
>had meant to include "ord" I would have said something like
>"substring". I meant prefix.

Well then, didn't you already answer the question when you
described changing the basis to the 2nds of the scale?

>> Right, and since it's not connected it can't be convex by the
>> definition I gave.
>
>Where did *you* give a definition?

It was potentially four definitions, and I asked which you prefer:
/tuning-math/message/19801

It seems we can already reduce it to two definitions, since
despite the preference I expressed it looks like all paths tied
for shortest must be tested.

>> >What is "A2"?
>>
>> The triangular lattice.
>
>I don't understand. Given that a lattice is defined as a Z-module, how
>is this lattice different from Z2? They seem to be the same lattice.

I define a lattice as a group
http://en.wikipedia.org/wiki/Lattice_%28group%29
In particular, I believe, an affine Coxeter group,
http://en.wikipedia.org/wiki/Coxeter_groups#Affine_Coxeter_groups
which are related to root systems. As I recall, modules have a
lot more horsepower, but Z2 has the same symmetry group as D2,
whereas A2's is different.

>Definition of "convex lattice set":
> /tuning-math/message/19781
>If your definition is different from mine you should give it a
>different name, because mine is the standard definition of "convex
>lattice set" among mathematicians who study discrete geometry. For
>example, http://books.google.com/books?id=WehCspo0Qa0C&pg=PA422 and
>http://books.google.com/books?id=MHVBQ2J7-9AC&pg=PA87 "Intersection of
>a convex body with the lattice" is equivalent to my definition, and I
>can prove it.

It's no secret you're far better at mathematics than I, so
there's no need to be a prick about it.

It's good that it's equivalent, since your version was over
my head. However it seems that for any convex body and its
intersection with the lattice, there are non-convex bodies
having the same intersection. Both should be convex according
to my definition, which is discrete and ought to be way
easier to compute.

-Carl

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
> > I don't see why the extra power of a module is required.
>
> There is no extra power. The same thing is sometimes called an abelian group, and sometimes called a Z-module. Keenan was calling it a Z-module, so I followed suit.

Right. Don't get hung up on the seemingly abstruse definition of "Z-module". As Gene said, it's the same concept as an abelian group, and all it is is a set of "vectors" where you can add vectors and you can multiply a vector by an integer.

The Z-module is the bare minimum amount of structure you need, because every property of a Z-module has an obvious musical interpretation. The zero vector is the unison. Every interval has an additive inverse, which is its inversion. You can add two intervals, and you can multiply any interval by an integer.

I question the musical relevance of any operations other than the basic Z-module ones.

In particular, Gene wrote:
> A lattice is usually considered to be a free Z-module of rank n discretely
embedded in and spanning a real inner-product vector space of dimension n. Hence Z2 and A2 are distinct lattices by this usual definition.

This extra structure seems musically irrelevant to me. What is the musical interpretation of the inner product operation?

Keenan

🔗Graham Breed <gbreed@gmail.com>

"Keenan Pepper" <keenanpepper@gmail.com> wrote:

> In particular, Gene wrote:
> > A lattice is usually considered to be a free Z-module
> > of rank n discretely
> embedded in and spanning a real inner-product vector
> space of dimension n. Hence Z2 and A2 are distinct
> lattices by this usual definition.
>
> This extra structure seems musically irrelevant to me.
> What is the musical interpretation of the inner product
> operation?

With Tenney weighting, it tells you the size of an
interval, although not directly in that the norm of an
interval is its complexity, not its size. More generally,
then, the inner product tells you the complexity, as a
generalization of Tenney harmonic distance. In the dual
lattice, cangwu badness is an inner product. It doesn't
translate very well back to ratio space. I think it is a
norm that tells you the badness of an interval, but it
doesn't work on matrices of unison vectors the same way
cangwu badness works on mapping matrices.

Graham

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> Well then, didn't you already answer the question when you
> described changing the basis to the 2nds of the scale?

What question do you mean - the question whether all 3-step, max-variety-4 scales are convex? No, I didn't answer my own question, because of the definition of "convex" I'm using.

> >Where did *you* give a definition?
>
> It was potentially four definitions, and I asked which you prefer:
> /tuning-math/message/19801

I don't prefer any of these definitions. I prefer the discrete geometry definition, which is equivalent to the one I gave.

> >Definition of "convex lattice set":
> > /tuning-math/message/19781
> >If your definition is different from mine you should give it a
> >different name, because mine is the standard definition of "convex
> >lattice set" among mathematicians who study discrete geometry. For
> >example, http://books.google.com/books?id=WehCspo0Qa0C&pg=PA422 and
> >http://books.google.com/books?id=MHVBQ2J7-9AC&pg=PA87 "Intersection of
> >a convex body with the lattice" is equivalent to my definition, and I
> >can prove it.
>
> It's no secret you're far better at mathematics than I, so
> there's no need to be a prick about it.

My apologies.

> It's good that it's equivalent, since your version was over
> my head. However it seems that for any convex body and its
> intersection with the lattice, there are non-convex bodies
> having the same intersection. Both should be convex according
> to my definition, which is discrete and ought to be way
> easier to compute.

You're correct that there are non-convex bodies having the same intersection. Given any non-empty subset of a lattice embedded in R^n, it's *always* possible to find a non-convex set in R^n having the same intersection with the lattice.

I don't understand what you mean by "both should be convex". Both *what* should be convex?

My definition is also discrete, and I didn't think it was that difficult to understand.

DEFINITION OF CONVEXITY:

In my book, a "convex set" is always defined as one that contains all "convex combinations" of its elements. It's only the definition of "convex combination" that's a little tricky in the discrete case.

In R^n, you can define a "convex combination" of a1,a2,...a_k as a linear combination c1*a1 + c2*a2 + ... + c_k * a_k where the c's are all non-negative and c1 + c2 + ... + c_k = 1. In other words it's a weighted average where all the weights are non-negative.

In Z^n, or any Z-module, to do this would require defining a "multiplication by real numbers" operation, which isn't part of the Z-module structure. But fortunately you can define convexity perfectly well using only the basic Z-module operations.

I say that b is a convex combination of a1,a2,...a_k whenever there exist non-negative integers c1,c2,...c_k such that

(c1 + c2 + ... + c_k) b = c1*a1 + c2*a2 + ... + c_k * a_k

This is clearly the same thing as saying b is a weighted average of all the a's (with the c's as the weights), but this definition uses only integers and the integer*vector multiplication operation.

Does anyone still have any problems with this definition??

Keenan

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:
> DEFINITION OF CONVEXITY:
>
> In my book, a "convex set" is always defined as one that contains all "convex combinations" of its elements. It's only the definition of "convex combination" that's a little tricky in the discrete case.
>
> In R^n, you can define a "convex combination" of a1,a2,...a_k as a linear combination c1*a1 + c2*a2 + ... + c_k * a_k where the c's are all non-negative and c1 + c2 + ... + c_k = 1. In other words it's a weighted average where all the weights are non-negative.
>
> In Z^n, or any Z-module, to do this would require defining a "multiplication by real numbers" operation, which isn't part of the Z-module structure. But fortunately you can define convexity perfectly well using only the basic Z-module operations.
>
> I say that b is a convex combination of a1,a2,...a_k whenever there exist non-negative integers c1,c2,...c_k such that
>
> (c1 + c2 + ... + c_k) b = c1*a1 + c2*a2 + ... + c_k * a_k
>
> This is clearly the same thing as saying b is a weighted average of all the a's (with the c's as the weights), but this definition uses only integers and the integer*vector multiplication operation.
>
> Does anyone still have any problems with this definition??

Gene, is this definition of "convex" equivalent to the one you've always been using?

Keenan

🔗genewardsmith <genewardsmith@sbcglobal.net>

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:

> In particular, Gene wrote:
> > A lattice is usually considered to be a free Z-module of rank n discretely
> embedded in and spanning a real inner-product vector space of dimension n. Hence Z2 and A2 are distinct lattices by this usual definition.
>
> This extra structure seems musically irrelevant to me. What is the musical interpretation of the inner product operation?

For one example, you may define symmetric lattices and the corresponding groups of transformations derived from isometries. For another, you may define Tenney-Euclidean metrics and hence TE tuning. For another, you may define temperamental complexity. For another example, you may define the Hodge dual when you extend consideration to wedge products. For another example, you may define the Frobenius projection map.

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
> --- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@> wrote:
>
> > Gene, is this definition of "convex" equivalent to the one you've always been using?
>
> Yes. I was thinking of it in terms of a Q-linear combination of elements summing to 1, but clearing denominators shows the equivalence.

Yeah, there we go, same thing.

Here is a "Convex scale" article for everyone's consideration:

http://xenharmonic.wikispaces.com/Convex+scale

Please edit it mercilessly, as if it were your own creation.

Keenan

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Mike Battaglia <battaglia01@gmail.com>

On Tue, Oct 18, 2011 at 8:37 AM, genewardsmith
<genewardsmith@sbcglobal.net> wrote:
>
> --- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> >
> > Gene wrote:
> >
> > >A lattice is usually considered to be a free Z-module of rank n
> > >discretely embedded in and spanning a real inner-product vector space
> > >of dimension n. Hence Z2 and A2 are distinct lattices by this usual
> > >definition.
> >
> > I don't see why the extra power of a module is required.
>
> There is no extra power. The same thing is sometimes called an abelian group, and sometimes called a Z-module. Keenan was calling it a Z-module, so I followed suit.

I thought that modules are differentiated from abelian groups in that
they have the scalar multiplication operation as well?

-Mike

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
> > There is no extra power. The same thing is sometimes called an abelian group, and sometimes called a Z-module. Keenan was calling it a Z-module, so I followed suit.
>
> I thought that modules are differentiated from abelian groups in that
> they have the scalar multiplication operation as well?

Modules (over arbitrary rings) are different from abelian groups, yes.

Modules over Z, however, are the same thing as abelian groups because you can just define na as (a + a + ... + a) where you have n copies of a. Whenever you have addition and additive inverses, you therefore have multiplication by integers.

So it's not "module" == "abelian group", it's "Z-module" == "abelian group".

Keenan

🔗Mike Battaglia <battaglia01@gmail.com>

On Tue, Oct 18, 2011 at 2:04 PM, Keenan Pepper <keenanpepper@gmail.com> wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
> > > There is no extra power. The same thing is sometimes called an abelian group, and sometimes called a Z-module. Keenan was calling it a Z-module, so I followed suit.
> >
> > I thought that modules are differentiated from abelian groups in that
> > they have the scalar multiplication operation as well?
>
> Modules (over arbitrary rings) are different from abelian groups, yes.
>
> Modules over Z, however, are the same thing as abelian groups because you can just define na as (a + a + ... + a) where you have n copies of a. Whenever you have addition and additive inverses, you therefore have multiplication by integers.
>
> So it's not "module" == "abelian group", it's "Z-module" == "abelian group".
>
> Keenan

OK, I got it. Thanks.

-Mike

🔗Carl Lumma <carl@lumma.org>

🔗Graham Breed <gbreed@gmail.com>

Carl Lumma <carl@lumma.org> wrote:
> Keenan wrote:
> >The Z-module is the bare minimum amount of structure you
> >need, because every property of a Z-module has an
> >obvious musical interpretation. The zero vector is the
> >unison. Every interval has an additive inverse, which is
> >its inversion. You can add two intervals, and you can
> >multiply any interval by an integer.
>
> I don't see why we need addition. Or, if you're still
> thinking of just intonation as having a basis containing
> things like log(p), I don't see why we need
> multiplication.

Let's talk about addition as the group operator.
Multiplication in a ring is different.

Quarter comma meantone is defined such that four fifths
give a 5:1. That requires the fifth to be multiplied by
4. What abelian group are you thinking of that wouldn't
allow that to happen?

Graham

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>

🔗Mike Battaglia <battaglia01@gmail.com>

On Tue, Oct 18, 2011 at 3:54 PM, genewardsmith
<genewardsmith@sbcglobal.net> wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> > I thought that modules are differentiated from abelian groups in that
> > they have the scalar multiplication operation as well?
>
> Every module is uniquely associated to an abelian group, the abelian group of the module elements on which the ring acts. What's different about Z-modules is that the module is also uniquely determined by the group: if "n" is any positive integer and x is a group element, then n*x = x+x+...+x n times. If n is a negative integer, then n*x = -(-n*x). Also, 0*x = 0. Since the abelian group and the Z-module are uniquely associated in this way, they can be identified.

OK, that makes sense. Thanks.

-Mike

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
>
> > http://xenharmonic.wikispaces.com/Convex+scale
> >
> >Please edit it mercilessly, as if it were your own creation.
>
> I'm guessing you didn't want me to cut the whole thing, so I'll
> comment here. First, it should probably be combined with the
> convex closure article. Second, the main paragraph is completely
> unclear. What are a1,a2...? What is b?

Ok, I guess you already figured out that there's no other article relating to convex scales yet, other than Gene's "Gallery of Z-polygon traversals".

The variables are just that, variables. The a's represent the vectors you're making a convex combination of, and b represents some other vector. I'm making a definition that says when b is a convex combination of {a1,a2...}.

If there exist integers {c1,c2...} such that

(c1 + c2 + ...) b = c1*a1 + c2*a2 + ...

then b is a convex combination of {a1,a2...}. If there exist no such integers, then b is not a convex combination of {a1,a2...}.

For any choice of vectors {a1,a2...} and b, this definition tells you whether b is a convex combination of {a1,a2...} or not. It seems weird to ask things like "What is b?" when b is just a variable I'm using.

Keenan

🔗Mike Battaglia <battaglia01@gmail.com>

On Tue, Oct 18, 2011 at 8:31 PM, Keenan Pepper <keenanpepper@gmail.com> wrote:
>
> For any choice of vectors {a1,a2...} and b, this definition tells you whether b is a convex combination of {a1,a2...} or not. It seems weird to ask things like "What is b?" when b is just a variable I'm using.

For Carl's reference, (because I was confused by this as well), a
convex combination of any 3 points is just a weighted average of those
points.

If you're not sure intuitively what a weighted average of points "is,"
consider a weighted average of the points (0,0) and (10,10) - anything
on the line (x,x) for 0<=x<=10 will be a weighted average of those two
points.

For 3 or more points, an more intuitive way to consider it is how much
"energy" each point ends up giving to the final combination. A good
way to intuitively visualize this is the RGB triangle:

http://www.ccs.neu.edu/home/fell/images/COM3370/hw0W97/sena.jpg

In this case, the bottom left point is #FF0000, the top is #00FF00,
the bottom right is #0000FF. Any point in between these on the
triangle is going to have some percentage of "energy" at each of those
three points - meaning it'll be a convex combination of the three
points. The RGB value at each point represents how much "energy" you
gave to each point, so in this case, every point is also a convex
combination of red, green, and blue. The point right in the middle of
the triangle is 33% red, 33% green, and 33% blue, so it's a crappy
blend of gray (#555555).

The take home point here is that all of these convex combinations have
to lay inside the triangle defined by the three fundamental "corner"
points. You'll never be able to take some weighted average of (0,0)
and (10,10), and get (1000,1000), and the same's true for triangles
and other shapes as well. If you work this out for sets involving more
than 3 points, you'll naturally discover that the shape that they all
have to lie in is actually the convex hull of the set.

In fact, this whole "convex combination" business is just a fancy way
of stating that all of the points inside the convex hull have to also
be in the set. If "convex combinations" seem abstract and unintuitive,
"point inside the convex hull" should do the trick - they're the same
thing.

All of Keenan's restrictions were basically that the weights have to
be positive - e.g. you can't have 110% red, -10% green, 0% blue - and
that they have to sum to 1. So you can't just have 30% red, 0% green,
0% blue. (There was an additional restriction about the weights having
to be rationals, but I didn't see the point in it).

-Mike

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

>The a's represent the vectors you're making a convex combination
>of, and b represents some other vector. I'm making a definition
>that says when b is a convex combination of {a1,a2...}.
>
>If there exist integers {c1,c2...} such that
>
>(c1 + c2 + ...) b = c1*a1 + c2*a2 + ...
>
>then b is a convex combination of {a1,a2...}. If there exist no
>such integers, then b is not a convex combination of {a1,a2...}.
>
>For any choice of vectors {a1,a2...} and b, this definition tells you
>whether b is a convex combination of {a1,a2...} or not. It seems weird
>to ask things like "What is b?" when b is just a variable I'm using.

Sounds like you'd have a grand time studying type theory.

If b is both a vector (useful info there) and a "convex
combination", I conclude that a convex combination of vectors
is also a vector. But a vector of what? Reals? Integers?
For now I'll assume it's in the same space as a1,a2... But
then I still have no idea what a convex combination has to do
convex scales.

Maybe I figured it out. For a scale a1,a2...an, I take the
2^n combinatorical combinations of its elements and find b
for each. Then if any of these bs weren't already an a, the
original scale wasn't convex, and if I add them, I get the
convex closure of the original. Correct? If so, you should
seriously consider saying so in your article.

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> Sounds like you'd have a grand time studying type theory.

Not sure what this means, or if it's a joke I don't get it. I know the very basics of what type theory is.

> If b is both a vector (useful info there) and a "convex
> combination", I conclude that a convex combination of vectors
> is also a vector. But a vector of what? Reals? Integers?
> For now I'll assume it's in the same space as a1,a2... But
> then I still have no idea what a convex combination has to do
> convex scales.

The a's and b are elements of the Z-module in question. I called them "vectors", but now I realize that's a slight error because it's a Z-module, not a vector space. Is there a word for elements of a Z-module other than "element of a Z-module"?

In the context of scales, the elements of the Z-module are intervals. They can also represent pitches, of course, if they're measured from some arbitrary 1/1 starting pitch. So this tells you when an interval is a convex combination of other intervals, or when a pitch is a convex combination of other pitches.

For example, 3/2 is a convex combination of 5/4 and 9/5, because 2(3/2) = 1(5/4) + 1(9/8).

> Maybe I figured it out. For a scale a1,a2...an, I take the
> 2^n combinatorical combinations of its elements and find b
> for each. Then if any of these bs weren't already an a, the
> original scale wasn't convex, and if I add them, I get the
> convex closure of the original. Correct? If so, you should
> seriously consider saying so in your article.

This isn't a concrete algorithm yet, because it's not enough to iterate over 2^n combinations of the intervals. You would have to iterate over all possible n-tuples of integers c1,c2...c_n, which is of course impossible because there are infinitely many.

Keenan

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:
>> Sounds like you'd have a grand time studying type theory.
>
>Not sure what this means, or if it's a joke I don't get it. I know the
>very basics of what type theory is.

You said it was strange to ask what b is, since it was just a
variable. At that rate I figured you'd succumb to anaphylaxis
if you took a course in type theory. :)

>The a's and b are elements of the Z-module in question. I called them
>"vectors", but now I realize that's a slight error because it's a
>Z-module, not a vector space. Is there a word for elements of a
>Z-module other than "element of a Z-module"?

Not that I know of, but the Z-module's elements are associated
with a vector space so "vector" is fine by me.

>> Maybe I figured it out. For a scale a1,a2...an, I take the
>> 2^n combinatorical combinations of its elements and find b
>> for each. Then if any of these bs weren't already an a, the
>> original scale wasn't convex, and if I add them, I get the
>> convex closure of the original. Correct? If so, you should
>> seriously consider saying so in your article.
>
>This isn't a concrete algorithm yet, because it's not enough to
>iterate over 2^n combinations of the intervals. You would have to
>iterate over all possible n-tuples of integers c1,c2...c_n,
>which is of course impossible because there are infinitely many.

Have you got something better?

For starters, why wouldn't considering only 2-combinations of
the elements work? Also, aren't c_n bounded between zero and
the diameter of the scale?

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> You said it was strange to ask what b is, since it was just a
> variable. At that rate I figured you'd succumb to anaphylaxis
> if you took a course in type theory. :)

Oh, gotcha. I didn't realize you were asking what kind of object b was, which is a perfectly valid question. It lives in the Z-module.

> >This isn't a concrete algorithm yet, because it's not enough to
> >iterate over 2^n combinations of the intervals. You would have to
> >iterate over all possible n-tuples of integers c1,c2...c_n,
> >which is of course impossible because there are infinitely many.
>
> Have you got something better?
>
> For starters, why wouldn't considering only 2-combinations of
> the elements work? Also, aren't c_n bounded between zero and
> the diameter of the scale?

The relevant example here is {(0,0),(1,2),(2,1)}. The point (1,1) is a convex combination of all three of those points, but it is not a convex combination of any pair.

It's not obvious to me that the c's are bounded by the diameter of the scale (what is "diameter" anyway?), but I feel like there has to be some simple bound. There also has to be some efficient algorithm for computing the convex closure of a set, which I'll try to come up with later.

But all this is about algorithms for computing things about convex sets, rather than the basic definition, which I believe should be perfectly clear now. No?

Keenan

🔗Carl Lumma <carl@lumma.org>

Trying to post this again:

Keenan wrote:
>> For starters, why wouldn't considering only 2-combinations of
>> the elements work? Also, aren't c_n bounded between zero and
>> the diameter of the scale?
>
>The relevant example here is {(0,0),(1,2),(2,1)}. The point (1,1) is a
>convex combination of all three of those points, but it is not a
>convex combination of any pair.

0,2-----1,2
/ \ / \
/ \ / \
/ \ / \
0,1-----1,1-----2,1
/ \ / \ /
/ \ / \ /
/ \ / \ /
0,0----1,0-----2,0

0,2---1,2
| |
| |
0,1---1,1---2,1
| | |
| | |
0,0---1,0---2,0

>It's not obvious to me that the c's are bounded by the diameter of the
>scale (what is "diameter" anyway?),

The usual graph-theoretic meaning. Both structures above have
diameter 3. One can see the set ((0 0) (1 1) (1 2) (2 1)) is
convex by your definition but not connected. To me, that casts
doubt on its usefulness in music theory.

Here's how I would compute my definition

(define convex?
(lambda (S)
(if (disjoint? S)
#false
(and
(map (lambda (pitch-pair path-length)
(eq? (lattice-distance pitch-pair) path-length))
(all-pairs-shortest-paths S))))))

There hardest part is all-pairs shortest path, and there very
efficient algorithms for it, especially for undirected
unweighted graphs.

>But all this is about algorithms for computing things about convex
>sets, rather than the basic definition, which I believe should be
>perfectly clear now. No?

Yes.

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> The usual graph-theoretic meaning. Both structures above have
> diameter 3. One can see the set ((0 0) (1 1) (1 2) (2 1)) is
> convex by your definition but not connected. To me, that casts
> doubt on its usefulness in music theory.

If you think convexity is useless, you don't have to talk about it ever. I happen to think it's important, so I'll continue to talk about it.

"Connected", of course, is not a property of the set in the abstract Z-module. You need to define some extra structure, for example an infinite graph, in order to say whether a set is connected. There are infinitely many distinct ways to do this. (This explains the confusion over Z2 and A2. Their Z-modules are the same but their graphs are different.)

> Here's how I would compute my definition
>
> (define convex?
> (lambda (S)
> (if (disjoint? S)
> #false
> (and
> (map (lambda (pitch-pair path-length)
> (eq? (lattice-distance pitch-pair) path-length))
> (all-pairs-shortest-paths S))))))

I believe my Scheme is good enough to understand this definition. But the following set seems to satisfy it:

0,5---1,5
| |
| |
0,4---1,4
| |
| |
0,3---1,3
| |
| |
0,2---1,2
| |
| |
0,1---1,1---2,1---3,1---4,1---5,1
| | | | | |
| | | | | |
0,0---1,0---2,0---3,0---4,0---5,0

Does this set indeed satisfy your definition? (If not, it might just be my rusty Scheme.) If so, I think "convexity" is a bizarre name for this property.

The property you've defined seems like it might be very useful, but you ought to choose a less misleading name for it, for example "shortest-path-connected" or maybe just "line-connected" for brevity. But any name other than "convex" would be fine with me.

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:

> > Here's how I would compute my definition
> > (define convex?
> > (lambda (S)
> > (if (disjoint? S)
> > #false
> > (and
> > (map (lambda (pitch-pair path-length)
> > (eq? (lattice-distance pitch-pair) path-length))
> > (all-pairs-shortest-paths S))))))
>
> I believe my Scheme is good enough to understand this
> definition. But the following set seems to satisfy it:
>
> 0,5---1,5
> | |
> | |
> 0,4---1,4
> | |
> | |
> 0,3---1,3
> | |
> | |
> 0,2---1,2
> | |
> | |
> 0,1---1,1---2,1---3,1---4,1---5,1
> | | | | | |
> | | | | | |
> 0,0---1,0---2,0---3,0---4,0---5,0
>
> Does this set indeed satisfy your definition?

Yes, but not the equivalent in A2

0,5---1,5
/ \ /
/ \ /
0,4---1,4
/ \ /
/ \ /
0,3---1,3
/ \ /
/ \ /
0,2---1,2
/ \ /
/ \ /
0,1---1,1---2,1---3,1---4,1---5,1
/ \ / \ / \ / \ / \ /
/ \ / \ / \ / \ / \ /
0,0---1,0---2,0---3,0---4,0---5,0

However, this one does

0,5---1,5---2,5---3,5---4,5---5,5
/ \ / \ / \ / \ / \ /
/ \ / \ / \ / \ / \ /
0,4---1,4---2,4---3,4---4,4---5,4
/ \ / ' '
/ \ / ' '
0,3---1,3....o
/ \ /
/ \ /
0,2---1,2
/ \ /
/ \ /
0,1---1,1
/ \ /
/ \ /
0,0---1,0

so the algorithm doesn't quite compute what I
thought it did. -Carl

🔗Carl Lumma <carl@lumma.org>

So here's another stab, and an algorithm that runs in better
than O(n^3) time where n is the number of notes (pitch classes).

It's designed for An lattices because they're known to be
highly relevant in music theory and because they ought to make
the computation easier. The lattices live in R^n Euclidean
space with unit distance equal in both.

1. find the Euclidean distance between all pairs of notes,
then cast out pairs with distance = 1 O((n^2)-n)

2. for each remaining pair and the straight line connecting
them, find the point-to-line Euclidean distance from each
other note O(n-2)

3. scale is convex IFF these distances are all <= r, where
r is the distance from a vertex to the centroid of the lattice
unit cell. For A2, r = 1/sqrt(3).

By this definition, this

0,1---1,1
/
/
0,0

is convex but this

0,1---1,1
/ \
/ \
0,0.........2,0

is not. Thoughts?

-Carl

At 10:22 PM 10/19/2011, I wrote:

>However, this one does
>
> 0,5---1,5---2,5---3,5---4,5---5,5
> / \ / \ / \ / \ / \ /
> / \ / \ / \ / \ / \ /
> 0,4---1,4---2,4---3,4---4,4---5,4
> / \ / ' '
> / \ / ' '
> 0,3---1,3....o
> / \ /
> / \ /
> 0,2---1,2
> / \ /
> / \ /
> 0,1---1,1
> / \ /
> / \ /
>0,0---1,0
>
>so the algorithm doesn't quite compute what I
>thought it did. -Carl

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> 1. find the Euclidean distance between all pairs of notes,
> then cast out pairs with distance = 1 O((n^2)-n)
>
> 2. for each remaining pair and the straight line connecting
> them, find the point-to-line Euclidean distance from each
> other note O(n-2)
>
> 3. scale is convex IFF these distances are all <= r, where
> r is the distance from a vertex to the centroid of the lattice
> unit cell. For A2, r = 1/sqrt(3).

I don't understand this algorithm. If you really mean find *all* the point-to-line distances and answer "convex" only if all of them are <= r, then sufficiently large triangles and convex hexagons doesn't satisfy this "convexity" property. For example:

0,2
/ \
/ \
0,1---1,1
/ \ / \
/ \ / \
0,0---1,0---2,0

The distance from the point (0,2) to the line through the points (0,0) and (2,0) is sqrt(3), which is greater than r, so this algorithm should return "false" for this convex triangle. Similarly,

0,2---1,2
/ \ / \
/ \ / \
0,1---1,1---2,1
\ / \ /
\ / \ /
1,0---2,0

The distance from the point (2,0) to the line through the points (0,1) and (1,2) is 3/2, which is greater than r.

On the other hand, if you made a mistake in step 2 and really meant find the *minimum* distance from the line to any other point in the set, then the definition is clearly too lax. The union of two convex sets that are arbitrarily far apart satisfies it.

> By this definition, this
>
> 0,1---1,1
> /
> /
> 0,0
>
> is convex but this
>
> 0,1---1,1
> / \
> / \
> 0,0.........2,0
>
> is not. Thoughts?

I guess the fact that you say the trapezoid there is not "convex" means you really did mean *all* point-to-line distances must be less than r, but that is a bizarre definition for "convex" because sets that satisfy it cannot be arbitrarily wide in both directions of the plane.

I *beg* you to stop using the word "convex" for these definitions of yours. The word "convex" already has an accepted meaning.

Keenan

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
>
> So here's another stab, and an algorithm that runs in better
> than O(n^3) time where n is the number of notes (pitch classes).

Since we're so concerned with algorithmic complexity now, I might as well give the obvious O(n*log(n)) algorithm for discrete convex hull in 2D.

("convex hull" == "convex closure")

This algorithm takes as input a set of n points in Z^2 and returns their convex hull as another set of m points. Its complexity is O(n*log(n) + m) which I believe is provably optimal. (Convex hull is equivalent to sorting, so n*log(n) is optimal, and you need time linear in m just to iterate over the output points.)

The restriction to Z^2 is not actually a restriction at all, because since this returns the real, honest convex hull, it is an affine invariant. To find the convex hull of a set of points in some arbitary lattice, simply do an affine transformation to Z^2, find the convex hull with this algorithm, and affine transform back.

1. Finding the vertices of the convex hull:

Andrew's monotone chain convex hull algorithm ( http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull ) works perfectly well in Z^2 with integer arithmetic. It runs in time O(n*log(n)) and returns two lists of points comprising the "upper hull" and "lower hull".

2. Finding all lattice points of the convex hull:

Merge the x coordinates of the points of the upper hull and the lower hull into the same list. We use the vertical lines through these x coordinates to partition the convex hull into disjoint trapezoids. Now it's an easy matter to loop through all integer x coordinates and yield the points that satisfy the two linear inequalities that correspond to being between the upper and lower edges of the trapezoid. Each test takes constant time, and we only loop through points that are actually close to being part of the convex hull, so this step takes time O(m).

Clearly, if you can compute the convex hull of a set in O(n*log(n)) time, then you can also test whether it's convex in the same time. Just take the convex hull and test whether it's equal to the original set.

Keenan

🔗Carl Lumma <carl@lumma.org>

Keenan wrote:
>> 3. scale is convex IFF these distances are all <= r, where
>> r is the distance from a vertex to the centroid of the lattice
>> unit cell. For A2, r = 1/sqrt(3).
>
>I don't understand this algorithm. If you really mean find *all*
[snip]
>On the other hand, if you made a mistake in step 2 and really meant
>find the *minimum* distance from the line to any other point in the
>set, then the definition is clearly too lax. The union of two convex
>sets that are arbitrarily far apart satisfies it.

Yes, I meant "any".

>> By this definition, this
>>
>> 0,1---1,1
>> /
>> /
>> 0,0
>>
>> is convex but this
>>
>> 0,1---1,1
>> / \
>> / \
>> 0,0.........2,0
>>
>> is not. Thoughts?
>
>I guess the fact that you say the trapezoid there is not "convex"
>means you really did mean *all* point-to-line distances must be less
>than r,

To be clear, the dotted line meant 1,0 is not in the set. Since
both 0,1 and 1,1 are > r from the dotted line, the set qualifies
as a hole. The smaller set above does not, since 0,1 is < r from
the line between 0,0 and 1,1. Unfortunately this means that any
symmetrical "L" will not qualify as a hole. Drat.

>I *beg* you to stop using the word "convex" for these definitions of
>yours. The word "convex" already has an accepted meaning.

They're just proposals. I wouldn't advance anything as a
definition of convexity unless it was equivalent to the
standard one or deviated for a good reason.

>> This suggests a related approach involving the notion
>> of a 'unit hole'. A convex scale would be one for which
>> the ratio between the Euclidean and taxicab distances
>> between every pair of notes is less than that across the
>> unit hole. That should be even faster to compute.
>
>I don't see how such a definition could possibly exclude the
>non-convex "L shapes" we discussed. Those L shapes already
>have the minimum possible taxicab distance between all
>pairs of points.

Yes, you're right.

>Since we're so concerned with algorithmic complexity now, I might
>as well give the obvious O(n*log(n)) algorithm for discrete convex
>hull in 2D.

You brought up algorithm efficiency, and it didn't sound so
obvious, when you wrote

>This isn't a concrete algorithm yet, because it's not enough to
>iterate over 2^n combinations of the intervals. You would have
>to iterate over all possible n-tuples of integers c1,c2...c_n,
>which is of course impossible because there are infinitely many.

and

>There also has to be some efficient algorithm for computing the
>convex closure of a set, which I'll try to come up with later.

-Carl

🔗Keenan Pepper <keenanpepper@gmail.com>

--- In tuning-math@yahoogroups.com, "genewardsmith" <genewardsmith@...> wrote:
> --- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@> wrote:
> > This extra structure seems musically irrelevant to me. What is the musical interpretation of the inner product operation?
>
> For one example, you may define symmetric lattices and the corresponding groups of transformations derived from isometries. For another, you may define Tenney-Euclidean metrics and hence TE tuning. For another, you may define temperamental complexity. For another example, you may define the Hodge dual when you extend consideration to wedge products. For another example, you may define the Frobenius projection map.

OK, these are all pretty neat things, but it's not like your saying "the musical interpretation of one interval 'dot' another interval is...". That was my point, that a Z-module is exactly what you need to represent the basic stuff like adding and subtracting intervals. The inner product operation is something extra you add (that could be defined different ways!) to get these fancy things.

More importantly for the overall discussion, convexity is independent of any extra stuff like an inner product. So, a set of pitches in 5-limit JI is convex in "A2" if and only if it is convex in "Z2". Right?

Keenan

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>

0,2-----1,2
/ \ / \
/ \ / \
/ \ / \
0,1-----1,1-----2,1
/ \ / \ /
/ \ / \ /
/ \ / \ /
0,0----1,0-----2,0

0,2---1,2
| |
| |
0,1---1,1---2,1
| | |
| | |
0,0---1,0---2,0

>It's not obvious to me that the c's are bounded by the diameter of the
>scale (what is "diameter" anyway?),

Here's how I would compute my definition

(define convex?
(lambda (S)
(if (disjoint? S)
#false
(and
(map (lambda (pitch-pair path-length)
(eq? (lattice-distance pitch-pair) path-length))
(all-pairs-shortest-paths S))))))

There hardest part is all-pairs shortest path, and there very
efficient algorithms for it, especially for undirected
unweighted graphs.

>But all this is about algorithms for computing things about convex
>sets, rather than the basic definition, which I believe should be
>perfectly clear now. No?

Yes.

-Carl

Very relevant paper, and the question I'm currently thinking about

🔗keenan_pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Graham Breed <gbreed@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗Graham Breed <gbreed@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Mike Battaglia <battaglia01@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗Keenan Pepper <keenanpepper@gmail.com>

🔗Carl Lumma <carl@lumma.org>

🔗genewardsmith <genewardsmith@sbcglobal.net>

🔗Carl Lumma <carl@lumma.org>