Typo in http://arxiv.org/.../0402051.pdf?

• Jim Kraai <jim.kraai_at_computility.com> wrote:

>> re: http://arxiv.org/ftp/cs/papers/0402/0402051.pdf
>>
>> In the following lines should 72 be replaced with
>> 73?
>>
>> Lemma 2. (4913+225)/(1594+73) is the next sibling
>> of (4913x+225)/
>> (1594x+73).
>>
>> Proof. As we already established in lemma 1,
>> parent encoding is (225y+b)/
>> (73y+d). Also in lemma 1 we nested Möbius
>> encoding y=21+1/x for node 21 inside
>> > its parent, and got resulting encoding
>> ((21*225+b)x+225)/((21*72+d)x+73).
>> If we were nested encoding y=22+1/x for node 22
>> instead, then, we would have got
>> > ((22*225+b)x+225)/((22*72+d)x+73). Given that
>> 21*225+b=4913 and
>> > 21*72+d=1594 we immediately have
>> 22*225+b=4913+225 and 22*72+d=
>> > =1594+72.
>>
>> With the help of lemma 1 we expect the next
>> sibling’s Möbius encoding to be
>> ((4913+225)x+225)/((1594+73)x+73)
>>
>> Question:
>> Given an existing node, when adding a new child
>> node, is there a
>> better way to find the 'next' or 'first' available
>> interval than to
>> SELECT the maximum a/c (from Matrix([a,c],[b,d])) in
>> the parent
>> interval?

The article contains one [insignificant] flaw. Rational encoding itself is not complete. Basically we need an extra boolean indicator in order to know when to terminate Euclidean Algorithm, since the same rational number would encode both 5.7.4 and 5.7.3.1 paths. This also relates to the determinant alternation property mentioned in one of the previous threads.

Matrix encoding is unambiguous, however. I'm planning to rewrite the whole article using matrices.

Here is an especially appealing number wall:

7187 0547 0076 0015 0001
0473 0036 0005 0001 0000
0092 0007 0001 0000 0000
0013 0001 0000 0000 0000
0001 0000 0000 0000 0000

(zeros are for ASCII aligning only)

The construction:

1. Fill in the main diagonal with all ones.
2. Fill in lower triangle with zeroes. (We don't really care about those values, except that filling them in a certain way preserves "determinant constraint" property below).
3. Choose any sequence of positive integers of length n-1 (Materialized path) and place it above the diagonal.

In the example, I've chosen 15.5.7.13.

4. Iterative Step. If we know the values a,b,c arranged in the wall into the 2x2 Matrix like this

? a
b c

then we calculate ? to meet the following constraint det(T)=?*c - a*b =
= case when "level of ? above the diagonal" is even then 1 else -1

For example

???? 0005
0007 0001

???? is in the second level above the diagonal, so that ????=(5*7+1)/1=36.

2x2 matrix in the top-left corner

7187 0547
0473 0036

is the matrix encoding of the path 15.5.7.13. In general, any 2x2 matrix of 4 adjacent values from this wall represents the subpath. For example,

0473 0036
0092 0007

represent subpath 5.7.13.

Here are the properties:
1. The 2x2 "determinant" formula. It's just a different wording for the above wall construction equation, which puts a constraint upon a 2x2 matrix of 4 adjacent values in the wall.

The determinant formula allows us to fill in the missing values as we move diagonally in the wall. We leveraged this formula in the iterative step when we filled in the wall by moving NW.

2. "Nonlocal" law:
T(n,m)=T(n,m-1)*T(n-1,n)+T(n,m-1)
For example:
7187=547*13+76

This law allows us to move in the wall while fill in missing values horizontally, except that we have to use path encoding numbers from the diagonal above the main diagonal. It is because of this reference to path encoding that I called this law "nonlocal".

3. The transposed law:
7187=473*15+92

This law allows us to move in the wall in vertical direction.

4. Matrix Product law:
[[92,7],[13,1]]*[[75,15],[5,1]]=[[7187,547],[473,36]]

Matrix Product law is reflection of path concatenation. Multiplying matrices is concatenating corresponding path strings.

Given parent, finding it's i-th child is easy. In the above number wall

7187 0547 0076 0015 0001
0473 0036 0005 0001 0000
0092 0007 0001 0000 0000
0013 0001 0000 0000 0000
0001 0000 0000 0000 0000

we know the parent matrix encoding

0547 0076
0036 0005

of 15.5.7

and we want to fill first and second rows in the first column. That's just straightforward application of the second property:

547*13+76=7187
36 *13+ 5= 473

Therefore the 13-th child encoding is:
7187 0547
0473 0036 Received on Tue Jun 22 2004 - 20:51:08 CEST