Smári McCarthy`s blagoblag on Yaxic.org

The diminution of irregularity is exemplified, amongst other things, in the case of staple products which supply our necessary food and clothing. With respect to them, famine and scarcity are by comparison almost unknown now, at any rate in tolerably civilized communities. As a consequence of this, and of the vast improvements in the means of transporting goods and conveying intelligence, the fluctuations in the price of such articles are much less than they once were. In other directions, however, the reverse has been the case. Fashion, for instance, now induces so many people in every large community simultaneously to desire the same thing, that great fluctuations in value may ensue.

- John Venn, The Logic of Chance (p 370-371)

 Written by John Venn (of Venn Diagram fame, unfortunately little else of his work has receive popular attention) in 1866. It shows that scarcity wasn’t even very real back then.

This is a nice reminder of how fun mathematics is. Thanks Vinay for the link.

Halli pointed out this great article.

Vinay blagged:

http://spectrum.ieee.org/print/4109

IEEE article suggesting that Metcalf’s law (value of a network equals the square of the number of users) is wrong, and the truth is more like n log(n).

Seems to me like this ought to be something one can check with, say, sale prices or other financial performance metrics.

I immediately had a thought on the subject: It may well be the case that both are right. That is to say, Metcalf’s law may be a “maximal value theorem”, while the IEEE article suggests a “mean value theorem”.

Let’s face it: Networks are rarely fully utilized, and indeed most networks grow more slowly as more users join them after a certain threshold point - one that your yacht club has far surpassed, and your national democracy has always been far beyond, but one that Facebook doesn’t seem to have slammed into (yet), and one that seems far off the horizon for the Internet in general.

The core question, I suppose, is one of connectivity: how well are individuals within the network connected and how strongly are the possible synergies within the network being utilized? If we assume that n log(n) is the average utilization, then we are talking about full utilization in small groups (under 4 people), but on average there is less than 7% utilization of possible communication pathways by the time you hit Dunbar’s number (150 individuals).

There’s definitely something there worth looking at.

White, Kopanski and Lipson wrote of Stochastic Self-Reconfigurable Cellular Robotics, but in their paper they used several slave automata and one master automaton that provided both power and logic to the swarm, coordinating the effort to self-reconfigure into a given shape. I’ve been thinking about this a bit and would like to repeat their experiment, but with completely autonomous asynchronous automata, each controlling or ceding control to others according to the results of some sensible system.

The problem is formulated like so:

When several autonomous asynchronous entities interact they frequently need to share knowledge in order to solve problems. Consider a group of square automata attempting to organize themselves into a predetermined pattern, where each individual automaton only has information about whether or not another automaton is connected to it on each of its four sides. As each only has very limited information about the global state they will, in order to complete their task, have to exchange information. The question is what information and how much of it?

The simplest (and most simplistic) solution is for all the automata to promiscuously share all information it has with all of it’s neighbors. The downside of this is that for n automata the space complexity of this is n²: if each automata is addressed by a 1 byte identifier then for 100 automata each has to have 10000 bytes of memory (~ 10 KB) at its disposal. For larger numbers of automata with larger addressing schemes (as 1 byte will only uniquely address up to 256 automata) this quickly becomes infeasable.

A more logical approach would be to consider the space as a bitfield and disregard any infomation about which automata are connected. This narrows the space complexity down to the size of the “playing field” (with 1 bit per location), but forces us to have a clearly defined playing field that each automaton can sense it’s location relative to the origin of, so that location information does not overlap or cause conflicts.

Is there another, simple scheme, which has very little space complexity (time complexity is of less interest), preferably being constant, and does not rely on the size or dimensions of the playing field?

Taken into analogy: At a dance each individual only has limited information about his position on the dancefloor, and in fact he does not care so much where he is as he cares whether or not he is about to bump into somebody else. Between him and his dancing partner they share, at any moment, a fairly detailed map of the global environment (i.e., the dance floor), but it would be cause prohibative for them to constantly inform each other of the location of every other individual (or wall) on the dancefloor. Rather, they take the more subtle approach of giving each other only information that the other unit needs to behave appropriately.

I went to see The Golden Compass on Saturday with Alli and Simmi. Good flick, really entertaining, and Dakota Blue Richards really pulled off her role with flying colors that, well, most of the other lead actors mostly weren’t there to follow up on.

However, the mathematician in me awoke to one facet of the movie. The eponymous compass (pictured) shows 36 symbols on its face, and there are three hands that select the parameters of the question, and one hand that returns the “truth”. Okay. So this is a function f: Z₃₆ × Z₃₆ × Z₃₆ -> Z₃₆. Which basically means there are only 46656 questions in existence, and only 36 different answers.

Granting leeway for contextual interpretation, we understand these 46656 questions are indeed innumerable - but it also means that every conceivable question can be reduced to one of 46656 proto-questions, or that there are indeed 46656 different sets, and each question belongs to at least one of these sets and no question belongs to any set outside of these. Further, there is a many-to-one relation mapping each of these 46656 sets to members of set consisting of 36 elements, giving us a reduction factor of approximately the cubic root.I really wish life were that simple.

But ignoring that kind of thing… it was a good movie. I look forward to the sequel. I wouldn’t mind reading the novels either… but the book Interface by Stephen Bury (a.k.a. Neal Stephenson & J. Frederick George) entered the top of my stack today when I accidentally ambled in to Nexus with Alli. Whoops.

I just finished reading Velimir Khlebnikov’s Artists Of The World!, in Anastasia Skoybedo’s translation as published in the Pusteblume Journal of Translation. Link (PDF). There he makes the assertion that certain sounds have correlation with certain geometrical properties and attempts to sketch a table of these sounds and properties whilst calling upon the artists of the world to create a writing system that accurately depicts this correlation.

     “Thus, from our landing of the staircase of thinkers it has become apparent that the simple bodies of language—the sounds of the alphabet—in essence name types of space, and are an enumeration of instances of its existence. The alphabet, common to many peoples, is a concise dictionary of spatial world, which is so close to your, artists, art and to your brush.”

Although this experiment will need several iterations before it reaches fruitition, I believe he may be on to something - something many others have been on to as well. From Neil Stephenson’s Mediaglyphics to John Wilkin’s Real Character (odd connection there) and throughout the entire omniglot repository, people are always trying to take language and abstract it to a level of maximal entropy: get as much out of every glyph as you can. The Chinese writing system is a great example of success in this, but simultaneously fails in many respects, as it is neither simple, concise, nor transparent although several base symbols are. (viz the Chinese glyphs for paddyfield, ⽥, and strength, ⼒, that combine to make the symbol for man, 男.)

But the reading of Khlebnikov’s text reminded me of the classical synesthesia experiment of Booba and Kiki. After having read quite a bit about synesthesia, and having actively sought out written works by known Synesthates, I’m leaning very much towards Richard Cytowic’s idea that synesthesia may be inherent in humans but to a varying degree, much like skin pigment, to take a frequently cited example of the variety of humans.

In part due to Cytowic’s promotion of the condition of synesthesia it has become something of a pop-syndrome, so to speak, along with Asperger’s syndrome in certain naïve circles of impressionable geeks. But that doesn’t change the fact that most of these conditions are quantitative rather than qualitative, and that some people may simply be more something than other people. (Insert obscure reference to the well ordering principle here)

So is there a geometrical connection between language and sound? I think so. Try it: Which is “Booba” and which is “Kiki”?

When you’ve answered correctly - as almost everybody does - go read Khlebnikov’s essay.

Also worth reading (in this context):

• The Man Who Tasted Shapes by Richard M. Cytowic
• Alice’s Adventures in Wonderland by Lewis Carroll
• Quicksilver by Neal Stephenson
• An Essay Towards a Real Character, John Wilkins

References:

• Pusteblume, Spring 2007 edition. Editor: Mathew Kelsey
• Codes, Ciphers and Other Cryptic and Clandestine Communications, Fred B. Wrixon
• The Kanji Dictionary, Spahn & Hadamitzky
• The Mathematics of Lewis Carroll, Smári McCarthy
• Synesthesia on Wikipedia

I got a phonecall from a physicist friend of mine today asking if I knew Fortran. “Uhm, no,” I replied, somewhat astonished. “I’ve never learned that.”

And I haven’t. Most people haven’t. And there’s a good reason for that. In the words of Edsger Dijkstra, “FORTRAN, the infantile disorder, by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too clumsy, too risky, and too expensive to use.”

But physicists use it a lot. Why? When I asked once, the answer I got was that Fortran was simply faster than any other language. “No,” I replied pointedly. It just isn’t true.

Fortran compiles down to native code much like C. Which means that fundamentally Fortran follows the same speed restrictions as C. Yes, not all compilers are as good as optimization, but that’s not a real issue.

A more important thing to recognize is Moore’s law and that it doesn’t really matter all that much any more which language you use. Yes, sure, fine, you’ll get your results a bit quicker using C than Java, but for most intents and purposes most languages are equal - although I still prefer using C for anything time-critical than Python, for example, which I use for almost everything else.

The thing about Fortran is it takes an age to make anything in it. The syntax is archaic and unintuitive and the language is stuck with 30 year old computer science concepts, most of which have long been exchanged for something better.

Consider for a moment a typical task for a Physicist: Calculating the value of exp(i*pi/2) and printing it out

Fortran (I wrote this myself after having consulted some examples on the net, it might be slightly wrong or overly complicated):

PROGRAM EXPCOMPLEXPIDIV2 IMPLICIT COMPLEX(X)

         PARAMETER (PI = 3.141592653589793, XI = (0, 1))

         X = EXP(XI * PI / 2)

         IF (AIMAG(X).LT.0) THEN

                  PRINT 2, 'e**(i*pi/2) = ', REAL(X), ' - i', AIMAG(X)

         ELSE
                  PRINT 2, 'e**(i*pi/2) = ', REAL(X), ' + i', AIMAG(X)

         END IF
END

Python equivalent:

from math import *

print "e**(i*pi/2) = %s" % (e**(1j*pi/2))

Let’s consider a more complicated example, solving a system of linear equations, Ax=b. (Copied from Wikibooks; I don’t know Fortran, remember!)

function GaussSparse(NumIter, Tol, b, A, X, ActualIter)

   implicit none

   real GaussSparse

   integer, intent(in) :: NumIter

   real, intent(in) :: Tol

   real, intent(in), dimension(1:) :: b

   real, intent(in), dimension(1:,1:) :: A

   real, intent(inout), dimension(1:) :: X

   integer, optional, intent(out) :: ActualIter

   integer i, n, Iter

   real TolMax, Xk

   n = ubound(b, dim = 1)

   TolMax = 2. * Tol

   Iter = 0   convergence_loop: do while (TolMax >= Tol.AND.Iter < NumIter); Iter = Iter + 1

TolMax = -1.

iteration_loop: do i = 1, n

         Xk = (b(i) - sum(A(i,1:i-1) * X(1:i-1)) - sum(A(i,i+1:n) * X(i+1:n))) / A(i, i)

         TolMax = max((abs(X(i) - Xk)/(1. + abs(Xk))) ** 2, abs(A(i, i) * (X(i) - Xk)), TolMax)

         X(i) = Xk

      enddo iteration_loop

   enddo convergence_loop

if (present(ActualIter)) ActualIter = Iter

   GaussSparse = TolMax

end function GaussSparse

And in Python, here’s the same (alas, not for a sparse matrix):

from numarray import dotdef gauss(A,b):

 n = len(b)

 for i in range(0,n-1):

 	for j in range(i+1,n):

 		if a[j,i] != 0.0:

 			lam = A[j,i]/A[i,i]

 			A[j,i+1:n] = A[j,i+1:n] - lam*A[i,i+1:n]

 			b[j] = b[j] - lam*b[i]

 for i in range(n-1,-1,-1):

 	b[i] = (b[i] - dot(A[i,i+1:n],b[i+1:n]))/A[i,i]

 return b

Nowadays, speed of development is more important than speed of execution because we can almost always just toss more computer at the problem - manpower costs more. This does not mean we can allow ourselves to be sloppy or to use overly heavy algorithms complexity wise, and we must still obey the laws of nature - which enforces bandwidth restrictions and convolution of data transmission functions over time (which we generally simply call lag), but it does mean that the idea that writing Fortran code will save you some time in the long run is simply wrong.

So to physicists (and those three other people who use Fortran) I say:

1. Learn Python, C++, or some other language that has at least some modern features.
2. Learn some complexity theory and get a good feeling for algorithm optimization - nowadays I can generally eyeball c.a. the big-O complexity of an algorithm with a fair degree of correctness. You should be able to work it out for yourself with little hassle.
3. Extra credit: is the Python version of the Gauss function faster or slower than the Fortran version?*

(*Answer: Without actually having calculated it, it seems to me that the Python version is roughly O(n log(n)), the Fortran version is roughly O(n²). Fortran code may run faster, but algorithm complexities are a lot more important than CPU cycles!)

I’ve been considering pricing models for a while. Let’s assume I have a marketplace that is available to people all around the world, where all products are free. However, to attract both more valuable products and more potential producers and consumers I want to allow people to sell their products, and yet I want to enforce a rule so that people pay only according to their means; that is to say, that given an object and a price, people living in Iceland pay for the object some portion of the price which is fair to them, while people in Malawi, currently the poorest country in the world, would still be able to afford it.

One method that came to mind was to create the vector G of all national GDP’s per capita (Purchasing Power Parity) and scaling them down by M = G * 1/max(G), and using that as a percentile of the price people from the respective country pays, making Malawians pay 0.8% of that which the Luxembourgois pay. This is fair, I believe, to the payer, but not to the payee. And it also puts Luxembourg and other top-GDP countries at a bit of a disadvantage.

I think the crux of it comes from how the price is initially defined. This is based on the product’s country of origin. So could we make an n×n matrix of all GDP PPP’s, G(G^T), and scale that to find a pricing matrix relevant to payers and payees?  That way Luxembourgois stand fairly equal to Icelanders and yet both are benefiting the poorer countries with a more comfortable pricing scheme.

Any ideas how is best to implement this? I’m not going to divulge what it’s for just yet… you’ll see.

A perfect number is a number where the sum of the integer divisors is the number itself. 6 = 3*2*1; 3+2+1 = 6. 6 is perfect. A few other perfect numbers are 28, 496 and 8128.

An amicable pair is a pair of numbers wherein the sum of the integer divisors of one are the other and vice versa. For example, the numbers {1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110} all divide the number 220, and their sum is 284. The numbers {1, 2, 4, 71, 142} divide 284 and their sum is 220.

From here we can introduce aliquot sequences. The word aliquot derives from Latin, aliquoties, meaning “several times”. An aliquot sequence is a sequence generated by a function s(n) for a natural number n such that the next value in the sequence is the sum of the divisors of the previous number. The Aliquot sequence for 6 is therefore 6, 6, 6, 6, 6, 6, 6, 6…. The aliquot sequence for 220 is 220, 284, 220, 284, 220, 284….

These sequences are frequently periodic, with the period 1 for s(6) and period of 2 for s(220) and s(284). Thus we define numbers to be perfect if their Aliquot sequence periods are 1 and amicable if their aliquot sequence periods are 2. Numbers with periods of 3 or larger are called Sociable numbers, and only Prime numbers have a period of 0. The only sociable set below 100000 is {12496, 14264, 14288, 14536, 15472}, which all have an aliquot sequence of period 5 containing the other four.

Some numbers, like 25 and 95 are called Aspiring numbers. The aliquot sequence for 95 is 95, 25, 6, 6, 6,… which shows that it does not start periodic, but eventually becomes periodic. The numbers 95 and 25 both aspire to become 6.

Some numbers seem to have infinite aliquot sequences. The most notable candidates are the Lehmer five: 276, 552, 564, 660, and 966. They are currently amongst the several hundred numbers below 100000 with undetermined aliquot sequences.

Now. I challenged Hörður to find all aliquot sequences of period seven wherein at least one number was less than 100000. Then I checked and found out there is none. But the checking took me several hours (I wrote the Python script in about 5 minutes with two layers of caching for speed, but it ran for hours). I’m wondering if there’s any smarter way to search for numbers with aliquot sequences of a certain period.

def divisors(n):
    res =[]
    for a in xrange(1, n):
        if n//a == n/float(a):
            res.append(a)
    return res

def d(n):
    return = sum(divisors(n))

Now finding out if the number 6 is perfect can be done with d(6) == 6, and to find if 220 is amicable one simply checks (d(220) != 220) and (d(d(220)) == 220). The first part of it is required to make sure that it is indeed amicable and not merely perfect.

To find if a number has an aliquot period of, say, 7, one needs to check that d(d(d(d(d(d(d(n))))))) == n and that nothing less is. Of course one would try not to make that kind of function call in reality, resorting rather to while loops, but still, it’s pretty horrific.

I’m thinking that significant speedups can be made by eliminating the two division points in the divisors() function, and if searching through the number space for amicable pairs or numbers with certain aliquot sequence periodicities use a lot of caching to speed up the calculations (as I did), but that’s the limit of what I can think of to make it go faster.

Any ideas?

def aliquot(n):
    m = n
    A = [m]
    while True:
        m = d(m)
        A.append(m)
        if m == 0 or m == n or len(s(m)) == 1:
            return A