StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This also turns out to be an abstract algebra problem. It's been awhile for me, but here's a few things to get started. There's nothing terribly significant about the following (it's all very basic; an expansion on the fact that every group is isomorphic to a permutation group), but it provides a different way of looking at the problem.</p> <p>I'll try to stick to fairly standard notation: "<strong>x</strong>" is a vector, and "<strong>x</strong><sub>i</sub>" is the i<sup>th</sup> component of <strong>x</strong>. If "L" is a list, <strong>L</strong> is the equivalent vector. "<strong>1</strong><sup>n</sup>" is a vector with all components = 1. The set of natural numbers ℕ is taken to be the positive integers. "[a,b]" is the set of integers from a through b, inclusive. "θ(<strong>x</strong>, <strong>y</strong>)" is the angle formed by <strong>x</strong> and <strong>y</strong></p> <p>Note <code>prodSum</code> is the dot product. The question is equivalent to finding all vectors <strong>L</strong> generated by an operation (permuting elements) on L2 such that θ(<strong>L1</strong>, <strong>L</strong>) less than a given angle α. The operation is equivalent to reflecting a point in ℕ<sup>n</sup> through a subspace with presentation: </p> <blockquote> <p>< ℕ<sup>n</sup> | (<strong>x</strong><sub>i</sub><strong>x</strong><sub>j</sub><sup>-1</sup>)<sub>(i,j) ∈ A</sub> ></p> </blockquote> <p>where i and j are in [1,n], <code>A</code> has at least one element and no (i,i) is in <code>A</code> (i.e. <code>A</code> is a non-reflexive subset of [1,n]<sup>2</sup> where |<code>A</code>| > 0). Stated more plainly (and more ambiguously), the subspaces are the points where one or more components are equal to one or more other components. The reflections correspond to matrices whose columns are all the standard basis vectors. </p> <p>Let's name the reflection group "RP<sub>n</sub>" (it should have another name, but memory fails). RP<sub>n</sub> is isomorphic to the symmetric group S<sub>n</sub>. Thus</p> <blockquote> <p>|RP<sub>n</sub>| = |S<sub>n</sub>| = n!</p> </blockquote> <p>In 3 dimensions, this gives a group of order 6. The reflection group is D<sub>3</sub>, the triangle symmetry group, as a subgroup of the cube symmetry group. It turns out you can also generate the points by rotating <strong>L2</strong> in increments of π/3 around the line along <strong>1</strong><sup>n</sup>. This is the the modular group ℤ<sub>6</sub> and this points to a possible solution: find a group of order n! with a minimal number of generators and use that to generate the permutations of L2 as sequences with increasing, then decreasing, angle with <strong>L2</strong>. From there, we can try to generate the elements <strong>L</strong> with θ(<strong>L1</strong>, <strong>L</strong>) < α directly (for example we can binsearch on the 1st half of each sequence to find the transition point; with that, we can specify the rest of the sequence that fulfills the condition and count it in O(1) time). Let's call this group RP'<sub>n</sub>. </p> <p>RP'<sub>4</sub> is constructed of 4 subspaces isomorphic to ℤ<sub>6</sub>. More generally, RP'<sub>n</sub> is constructed of n subspaces isomorphic to RP'<sub>n-1</sub>.</p> <p>This is where my abstract algebra muscles really begins to fail. I'll try to keep working on the construction, but Managu's answer doesn't leave much hope. I fear that reducing RP<sub>3</sub> to ℤ<sub>6</sub> is the only useful reduction we can make.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload