Tuesday, July 9th, 2013

Random Matrix Algebra

I've been getting familiar with the Sage environment. Here's a nontrivial result (but I dunno how interesting it is) about eigenvalues.

Take the finite field GF(3), and look at all its 3x3 matrices. How many of these 39 = 19683 matrices' characteristic functions have all three roots? Or no roots? Brute force search reveals:

roots 	count
() 	3456
(0) 	2106
(1) 	2106
(2) 	2106
(0,0,0) 	729
(0,0,1) 	1054
(0,0,2) 	1053
(0,1,1) 	1052
(0,1,2) 	1404
(0,2,2) 	1053
(1,1,1) 	729
(1,1,2) 	1053
(1,2,2) 	1053
(2,2,2) 	729


No cubic in GF(3) has just two roots for the same reason as cubics in the reals don't have just two real roots, I think. The element of a field extension in which those two extra roots exist must cancel out. But in GF(3) you've got degree-three extensions too, so zero-root polynomials exist as well.

What's potentially interesting here is the symmetry breaking for (0, 0, 1) and (0, 0, 2). Those cases have +1 and -1 count, respectively, than you would "expect" by comparison with (0, 0, 1), (1, 1, 2), (0, 1, 1), and (1, 2, 2). The single-root cases are perfect symmetric, by contrast.

Anyway, since these roots are the eigenvalues it turns out that just slightly over 50% of the 3x3 matrices in GF(3) have the full set of eigenvalues (and thus might be diagonalizable, although probably a lot are defective.)

Expanding to 4x4 matrices (43 million of them) or GF(5) (about 2 million) would require a lot more processing time, so I'd like to make the computation smarter in some way.
(1 comment | Leave a comment)

Sunday, June 16th, 2013

Mathy thing I learned today

V. K. Leont’ev, Roots of random polynomials over a finite field, 2006 (payment required but you can see the first couple pages.)

As the size q of a finite field Fq grows larger, the number of roots of a random polynomial from Fq[x] asymptotically becomes a Poisson distribution with mean value 1. That is, for large finite fields, a random polynomial can be expected to have just one root within the finite field.

So if random matrices give rise to uniformly distributed characteristic polynomials (which I'm not at all sure is the case) then we can expect random matrices over finite fields to have just one eigenvalue, on average.
(Leave a comment)

Sunday, May 19th, 2013

Classic Math Geek Sunday

...will not become a regular feature, unlike timprov 's classic photos.

But I did get a question from a high school student about a calculation I'd done about the game Tonk, five years ago on 2+2: http://forumserver.twoplustwo.com/21/draw-other-poker/profitably-dropping-tonk-315444/

I didn't mention the technique in the forum post, but I used a generating function to count the possibilities. If you multiply (1+yxk) together for each value of "k" in the deck (as a multiset, not a set), you get a polynomial whose coefficient on yixj is the number of ways to make a "j"-point hand with "i" cards.

Back in 2008 there wasn't a readily available symbolic manipulation tool available on the web, so I hacked some python together to do the math. Today there's Wolfram Alpha, whose limited-duration (free) computation is powerful enough to give:

simplify | Coefficient[(1+y x)^4 (1+y x^2)^4 (1+y x^3)^4 (1+y x^4)^4 (1+y x^5)^4 (1+y x^6)^4 (1+y x^7)^4 (1+y x^8)^4 (1+y x^9)^4 (1+y x^10)^16, y, 5] as

4368 x^50+7280 x^49+10640 x^48+16720 x^47+22496 x^46+31216 x^45+40436 x^44+52556 x^43+65532 x^42+82176 x^41+92548 x^40+105176 x^39+116832 x^38+127484 x^37+136344 x^36+143676 x^35+147784 x^34+149268 x^33+146936 x^32+140224 x^31+134052 x^30+125188 x^29+115520 x^28+103808 x^27+92416 x^26+79416 x^25+67600 x^24+55712 x^23+45584 x^22+36708 x^21+28948 x^20+22144 x^19+16520 x^18+11988 x^17+8344 x^16+5724 x^15+3784 x^14+2492 x^13+1552 x^12+920 x^11+484 x^10+240 x^9+92 x^8+28 x^7+4 x^6


which (fortunately) seem to be the numbers I came up with in October 2008.

I wonder how well Wolfram Alpha's freemium model is working for them. :)
(4 comments | Leave a comment)

Monday, May 13th, 2013

Late-night group theory

Nearly every undergrad who takes abstract algebra learns the proof that the 15-puzzle cannot be solved if two of the tiles are reversed. That's because the permutations generated by the sliding motions are a subset of the entire permutation group (Sn), called the alternating group (An). The alternating group contains permutations that can be expressed as an even number of transpositions (called, unsurprisingly, "even permutations"), and a single-tile swap is an odd permutation.

So what if the motions are instead wraparound "slides"? That is, take an entire row or column and move it as many squares as you want, with tiles wrapping around from left to right or top to bottom. Does that set of moves produce the entire permutation group? Or is it the alternating group, or some other subgroup?

For odd-sized grids, the slide moves produce just even permutations. For example, sliding the top row on a 3x3 puzzle like this:
 3  1  2
 4  5  6
 7  8  9

is the cycle (1 2 3) = (1 3)(1 2), which is even.

For even-sized grids it seems possible to generate a single-transposition--- say, (1 2)--- since the slides are odd permutations, but how to prove it?

Well, one way is brute force. For a 4x4 grid it might be just feasible to find the shortest "word" (combination of generating moves) which generates a particular transposition, although the search space is of size 16! =~ 2*10^13. I thought for a bit and bounded depth-first-search seemed better than BFS or heuristic search, because the queue size could become very large. But the size grows very quickly, even with two pruning heuristics at work.

The 8 basic moves on a 4x4 grid are H1, H2, H3, H4, V1, V2, V3, V4, where Hy slides the y'th row right by one, and Vx slides the x'th column down by one. The reverse moves can be generated by cycling around, i.e., H1^-1 = H1.H1.H1. So there are two easy ways to prune the DFS tree. The first is that we should never use the same move more than three times in a row. The second is that all the H's commute with each other (and so do all the V's), so we shouldn't explore both H3.H2.H1 and H1.H2.H3 since they are the same.

Depth   # of words    (w/o pruning commutative pairs)
4            2443          4673
6           95883        298057
8         3761907
10      147594811
12     5790738743


So much for brute force--- we didn't find (1 2) in this search, and going to 14 would take more than overnight.

But, that undergraduate algebra class probably talked about commutators as well, moves of the form y^-1.x^-1.y.x. In solving a Rubik's cube these moves tend to swap just a subset of the cubes, making it easier to find a move which fixes a portion of the cube while leaving the rest alone. The same is true here. (Note that composition of group operators is read from right to left.)

A useful commutator, X = V2^-1 . H1^-1 . V2 . H1 (first row right, second column down, first row left, second column up) introduces a 3-cycle among 1, 2, and 14:
*14 *1  3  4
  5  6  7  8
  9 10 11 12
 13 *2 15 16


So V2.X.X produces the desired swap of 1 and 2, but has messed up the column:
[2   1] 3  4
 5 *14  7  8
 9  *6 11 12
13 *10 15 16


But, another three-cycle can be used to correct this. Let Z = V2^-1 . H3^-1 . V2 . H3, which looks like this:
 1   2  3  4
 5 *10  7  8
*6  *9 11 12
13  14 15 16

We just need to move the '10' into position, perform the cycle, and then back out again. That means something of the form Y^-1.Z.Y, where Y = V1^-1 . H4^-1. Here's Y alone:
 5  2  3  4
 9  6  7  8
14 10 11 12
 1 15 16 13

which screws up a bunch of stuff, but here's Y^-1.Z.Y:
 1   2  3  4
 5 *10  7  8
 9 *14 11 12
13  *6 15 16

which is a nice well-behaved three-cycle, exactly the one we want to patch up V2.X.X. Putting it all together, Y^-1.Z.Y.V2.X.X =
 2  1  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

or in word form: H4.V1.V2.V2.V2.H3.H3.H3.V2.H3.V1.V1.V1.H4.H4.H4.V2.V2.V2.V2.H1.H1.H1.V2.H1.V2.V2.V2.H1.H1.H1.V2.H1. There might be a shorter word for the same permutation, but at 33 moves we were not likely to find this one by brute force any time soon.

But, this is sufficient to show that the slide moves generate the whole symmetric group S_16, since we can generate any other desired transposition in the same way, and the transpositions are generators for S_16.

How could we encode the directed search I performed by hand, into a computer algorithm for finding efficient (but not necessarily minimal) sets of moves for a given permutation?
(3 comments | Leave a comment)

Tuesday, May 7th, 2013

Towards a Taxonomy of Match-3 Games

Field: square lattice, hexagonal lattice, freeform, 1-d

Moves: slide (15-puzzle style), rotate around lattice "great circle", rotate around interior point, swap, drop (singles or groups, with restricted placement at edges), place (arbitrary free location)

Matching result: promote/build (objects are combined to a next-tier object), clear

Minimum match size: 3, 4, 5+

Slide Lattice rotation Point rotation Swap Drop Place
Clear Puzzle Pirates "Navigation" (cylindrical topology), PopCap Chuzzle Puzzle Pirates "Foraging", KadoKado "Binary" (match-4) PopCap Bejeweled, Puzzle Quest, Puzzle Pirates "Bilging" PopCap Zuma (1-d, single unit), KadoKado "Paradice" (multiple units in parallel, match-4), KadoKado "Drakhan" (single unit, freeform), Puzzle Pirates "Sailing" (two-unit), Dr. Mario (two-unit, match-4) PopCap Alchemy (match-6)
Promote Alien Hive Naturalchimie (2-unit drops) Spryfox Triple Town

I am sure I have seen a "clear"ing game with the slide-to-empty-space mechanic, but I cannot come up with it. "Alchemy" is something of a cheat.

I am less sure that the "promote" row can be filled in. So many games use the swap mechanic that I feel like there must be a "build+swap" game but I can't think of one.

One obvious variation is to perform rotations around the center on a square grid. I.e., the center rotation would move 4 squares, the one outside that would move 12 squares, the next ring has 22 squares.

(4 comments | Leave a comment)

Saturday, April 6th, 2013

MinneBar 8

MinneBar 8 has come and gone. I had a good time, as usual, and touched base with a lot of friends who were attending.

"All the Monitoring" by Bryan Brandau from Best Buy: good overview of monitoring tools (other than Nagios). Showed Sensu, Graphite, Logstash. What the heck is up with all the different open-source dashboard projects, though? He mentioned at least five by name.

"Agile Financial Modelling" by the Investyr guys. A little weak, their main point was not to spend a bunch of time on useless stuff--- put a quick spreadsheet together spending 80% of your time on year 1, 15% on year 2, don't bother beyond year 3. I wish they had done more with showing what sort of scenarios you could play with once you had a spreadsheet in place, instead they actually built it on the fly.

"Do 'Data Science'" by a bunch of folks from NativeX. I walked out of this one--- should have gone to learn about Julia or attend the lightning talks instead, but both rooms were packed. The presentation was dull and process-oriented to start, and included an explanation of Bayes' Theorem that was tedious to those who already knew it and probably confusing to those who didn't. Really would have been a ton better if they'd started with "here's what we did for the company, want to learn how we did it" rather than some bogus "we follow the scientific method unlike you uncultured barbariansengineering types" . (I mean, they quoted this PhD comic but failed to notice that real science is more like the joke version--- that's the funny.)

Technical Support for Developers panel by Chris Warren, Luke Francl, and Kevin Whinnery. This was a lot of fun. The support they provide is mainly API support rather than purely end-user but they had good stories comparing different approaches (dedicated team vs. development team) and the value of direct customer feedback.

Shopping for Nerds by Neal Tovsen. This was a brief talk on how to weigh the risks of different technical "talent": outsourcing, freelancers, co-founder, etc. I think Neal accurately described the trade-offs, and his point that you need to make sure somebody is "looking out for you" is well taken. But the session could have been stronger with more examples to help illustrate what has worked and what hasn't--- we mainly got some (usually anonymized) horror stories.

I asked whether anybody in the room had actually been successful at throwing out their outsourced/cobbled-together MVP and building the "real" product afterwards. Nate Yourchuck said he's done a couple of consulting projects where he built a real product to replace emailed-around Excel spreadsheets. I remain dubious that you can really "build one to throw away" (pace Fred Brooks.)

I got to hear Neal give his pitch for "Apruve" several times today and yesterday, and I think there is quite a bit of potential there.

Journey to the Bottom of the Storage Stack by me. I thought it went pretty well, but I suspect I spoke too quickly. Also I kept wandering too close to another live microphone and causing feedback. My friend Scott brought a friend from Isilon along to keep me honest. That gentleman suggested an alternate proposal for an anomaly I'd found, of hot data blocks pointed to be cold metadata--- that frequently-written metadata blocks might never be flushed from the journal. I'm dubious, I don't know if ext4 actually implements that optimization.

Slides will go up on the Minnestar wiki within the next few days, hopefully.

Scaling with Cassandra by Jeff Bollinger + another NativeX (nee W3i) guy. Talked about why they chose to move from SQL Server to Cassandra, and about Cassandra's data and consistency model.

The numbers they gave for their production system: 12 nodes (each running 12 cores @ 2GHz) with 2x480GB commodity Intel flash drives. Per node they see about 240 writes/sec peak, and 888 reads/sec. (These numbers seemed low, I think they are observations rather than benchmarks.) They see about 3ms writes, 4ms reads (end-to-end) which is not too bad considering the extra network hop, but not blazing fast--- their SQL server achieves 1.5ms read latency, but most of the data is in memory after moving bulk data to Cassandra. Their solution is hybrid now, they kept SQL for the data that really was relational, and talked about the importance of understanding the data movement characteristics while doing the design. Jeff also mentioned that it took them a few times to get the hardware right, so they wished in retrospect they'd done more prototyping and experimentation using cloud resources instead of in-house boxes.

I always feel like I should stick around longer during the happy hour, but as usual I had had about all the monkeys I could take, and even on the edges of the large cafeteria area the conversational noise is quite high.
(Leave a comment)

Friday, January 18th, 2013

Neighborly Sequences

In an arithmetic sequence --- for example, 1, 4, 7, 10, 13, 16, 19 ... --- each number is the arithmetic mean of its neighbors. (In fact, it is the arithmetic mean of all of its N predecessors and N successors.)

In a geometric sequence (1, 4, 16, 64, 256, ...) each number is the geometric mean of its neighbors. And again this can be expanded to the N closest neighbors.

What other "aggregate" functions can produce sequences of this sort? For example, "max()" and "min()" produce only the constant sequences.

The "mex" function (minimum excluded number) produces a cyclic sequence, but cannot be expanded from one neighbor to multiple neighbors. For example,

mex( 0 ) = 1
mex( 0, 1 ) = 2
mex( 1, 2 ) = 0

produces the sequence 0, 1, 2, 0, 1, 2, .... Taking two neighbors produces the same sequence, a promising start!

mex( 0, 1, 0, 1 ) = 2
mex( 1, 2, 1, 2 ) = 0
mex( 2, 0, 2, 0 ) = 1

But mex( 0, 1, 2, 1, 2, 0 ) = 3. In fact I think we could show that 0, 1, 2 repeating and 0, 2, 1 repeating are the only possible mex-based sequences.

How about 'median'? Or '90th percentile'? Median works fine for any increasing sequence, if you include the number itself.

In general, what conditions on F: 2N -> N are necessary and sufficient so that a sequence s0, s1, s2, s3, ... exists with F( sn-k, sn-k+1, ..., sn, sn+1, ..., sn+k ) = sn? What if we require the sequence to be nonrepeating?
(Leave a comment)

Saturday, October 20th, 2012

Rapture Denied

I finished Rapture of the Nerds today, about which Marissa has more to say in her review. Their future is one in which the inner planets (except Earth, although the fate of Luna was not mentioned) have been disassembled to build orbiting computational substrates, which form a cloud around the sun in order to harvest its energy. Uploaded humans live at speeds greater than real-time.

I felt like the issue of lightspeed delay was mentioned but not really handled. Let's crunch some numbers. Or at least as many numbers as don't require me to perform calculus.

Let's assume the asteroid belt is included but no outer planets (which are mentioned as future work.) It doesn't make sense to disassemble Venus until you've scooped up all the small planetesimals first! So we're talking a radius of about R = 3.27 AU = 4.9*1011 meters. Although the past-rapture nerds could limit themselves to in-plane orbits, this is wasteful of sunlight so we should assume a sphere.

The speed of light is 3*108 m/s, so the maximum volume with which you can hold a conversation at 10ms round-trip latency has (5ms * c) radius = a mere 1500km. Now, 10ms latency is way less than humans need. But if you're living at 100x speedup then that's a perceptual second.

Suppose you want "common knowledge" (say, a fully-functional simulation of Earth) to be accessible at no more than a 1-second perceptual delay. How many times would a particular record need to be replicated within the cloud? R^3 / (1500km)^3 gives us about 3.5*1025 copies. This is the first hint that the computational infrastructure doesn't scale well.

(We can improve matters by sticking to the surface of a sphere rather than distributing nodes throughout its volume, but that makes the average case delay for uncommon information worse!)

Of course, if there are only say 1012 (a trillion) posthuman entities floating around, they can just take the data with them wherever they happen to be. But what about *uncommon* knowledge, like the consciousness of a particular individual?

Let's imagine the best possible case in which you're tucked neatly within the orbit of Mercury. By sending a signal a distance of D you can reach D^3/R^3 of the total storage capacity (at latency 2D/c). If data is uniformly distributed, then the probability of finding a unique datum within a given time limit is as follows:

ProbabilitySubjective seconds at 100x speedup
1%70,000 seconds (~19 hours)
2%24.6 hours
5%33 hours
10%42 hours
20%53 hours
50%72 hours


In other words, the Singularity is not like a universal jukebox so much as a universal Amazon.com: you can find anything you want, but it'll probably take two days to get it. It seems a better bet for a Solar System-spanning electronic culture to run at slower than realtime.

spoileryCollapse )
(1 comment | Leave a comment)

Friday, October 5th, 2012

gcd's of infinities

A standard construction, courtesty of Wikipedia:

The non-negative integers, ordered by divisibility [form a Complete Lattice]. The least element of this lattice is the number 1, since it divides any other number. Maybe surprisingly, the greatest element is 0, because it can be divided by any other number. The supremum [join] of finite sets is given by the least common multiple and the infimum [meet] by the greatest common divisor. For infinite sets, the supremum will always be 0 while the infimum can well be greater than 1. For example, the set of all even numbers has 2 as the greatest common divisor. If 0 is removed from this structure it remains a lattice but ceases to be complete.


What if we wanted to take this in a nonstandard direction instead? We could imagine some sort of transfinite number that was divisible by all powers of two but not by any other number, call it Ω2. The join of the (infinite) set of numbers divisible by three is then Ω3, and join( Ω2, Ω3 ) = Ω6, naturally. I don't think these behave like the surreal numbers 2ω, 3ω, etc., because I think 3 divides the surreal 2ω = ω + ω but not the "2^infinity" Ω2. (But I'd have to do some more work to be sure.) I would also need to do research to see whether 2ω, 3ω are well defined and fit the bill--- exponentiation is tricky.

It seems like there are two possibilities. Either somebody has already invented this structure and given it a name, or else the idea contains some contradiction. But I don't yet know enough to determine which is the case. :)

Tangentially related: Transfinite Chomp, but there the lattice looks much different.
(Leave a comment)

Monday, September 10th, 2012

At least one CCG is Turing-Complete

How to implement a Turing Machine with M:tG cards. This is a pretty impressive reduction.

It's not an extremely surprising result. Once you have pattern-matching and some mechanism for unbounded state, you're pretty close to universal computation. In fact, one of the themes I picked up from reading "Games of No Chance" is how hard it is to prove that many games are actually in PSPACE or EXPTIME instead of something worse (EXPSPACE or uncomputable.)

But a very impressive engineering effort; his "widgets" are quite clever.
(Leave a comment)
Previous 10 | Next 10