Author: mathman

Ducci sequences – Part one

Posted on by mathman

In previous post we explained what Ducci sequences are. In this article we will prove several properties.

First of all let’s do some exploration and try several things. We will be interested in long term behaviour. For that define Ducci map D: \mathbb Z^n \rightarrow \mathbb Z^n as D(v) = (∣v_1​-v_2​∣,∣v_2​-v_3​∣,…,∣v_n​-v_1​∣). Now what will happen if we will use D repeatedly?

If v is zero vector, it is simple, D^k(v) = (0, 0,..., 0) for any k. If we take only one non zero component, we get for example this D^2((1,0)) = D((1, 1)) = (0,0). Do we always get zero vector? No, for example D^4((1, 0, 0)) = D^3((1, 0, 1)) = D^2((1, 1, 0)) = D((0, 1, 1)) = (1, 0, 1) and we get a cycle (starting with (1, 0, 1)).

What if we try some more complicated vector, like (3, 5, 2). Then we get by repeated applying of Ducci map -> (2, 3, 1) \rightarrow (1, 2, 1) \rightarrow (1, 1, 0). Again, we got just binary vector! Does that happen always?

Unfortunately no, for example

(10, 20, 30) \rightarrow (10, 10, 20) \rightarrow (0, 10, 10) \rightarrow (10, 0, 10) \rightarrow (10, 10, 0) \rightarrow (0, 10, 10)

and we obtain a cycle. But notice that everything in the cycle is scalar multiple of binary vector! So our first hypothesis would be that after some time we get a binary vector or its multiple.

We will use two theorems to prove it.


Theorem 1: Let v be vector with integer components v = (v_1, v_2,..., v_n) and let weight be maximum of these components, ie. w = max\{v_1, v_2, ..., v_n\}. Then applying Ducci operation cannot increase this weight.

Proof of Theorem 1. Let w be weight of some vector (v_1, ..., v_n). After applying Ducci once, we get another vector (|v_1-v_2|, ..., |v_n-v_1|. But we know that |v_i - v_j| \leq max(v_i, v_j), from which the conclusion follows. QED

Now we know that weight is not increasing. In order to prove our claim about having binary vector, we have to think about non binary vectors which are not multiples of binary vectors. If we look for example at (5, 0, 2), there are two possibilities that can come to your mind. If the weight does not decrease, all entries will have to be zero and one of them will have to be 5. Second thought is that weight always decreases for vectors like these. This thought is the right one.

Theorem 2:
Let n \geq 2 be an integer, and let v=(v_1​,v_2​,…,v_n​) be a vector with integer components and weight m, which is not binary nor scalar multiple of it. After finitely many iterations of D, the weight decreases; that is, W(D^k(v))<m for some k \geq 1.

Proof of Theorem 2. The main idea behind this proof is that either the weight decreases or the maximum number of zeroes after maximum decreases. Because both can happen finitely many times, it proves our theorem.
To be more specific, if you have non zero number right after maximum, this entry decreases in the very next step. If not, then there are several zeroes next to it, so it looks like this (b, m, 0,..., 0, c), where b is any number \leq m, m is maximum and c is any number \leq m. Look at the number of zeroes next to m – after this many steps plus one the m decreases by c.

The problem of course is – what if after m decreases, another entry increased to m? For example if you begin by (0, 10, 2, 0), you get to (2, 6, 2, 10). But it is not problematic, since the number of zeroes decreases in a vector that is not binary nor multiple of binary vector.

So because of these facts, we can work only with binary vectors since we know we would always get to them after finitely many steps or to multiples of them, but they behave exactly the same.

Ducci seqeunces – intro

Posted on by mathman

Take any vector with real numbers as entries, say a_1, a_2, ..., a_n and produce new vector, namely |a_1 - a_2|, |a_2 - a_3|, ..., |a_n-a_1|. You can imagine it as having the numbers in cirlce, going clockwise and taking differences. Then iterate this operation. The sequence of vectors we obtain is called Ducci sequence.

For example if we set n = 3 and take (7, 4, 10), we obtain this sequence (7,4,10)\rightarrow (3,6,3) \rightarrow (3, 3, 0) \rightarrow (0, 3, 3) \rightarrow (3, 0, 3) \rightarrow (3, 3, 0) and we got a cycle with period 4.



Convergence is obviously the thing one will think about as one of the very first things. There are some nice results we will explore, for example that any n-tuple converges to some multiple of vector with entries only from \{0,1\}. We will call vectors like these “binary vectors”. Our first step will be to understand proof of this claim.


Because it converges to vector like that and we will care about vectors with integer inputs, we will know for sure we actually get to multiple of vector with inputs only with inputs from \{0,1\}

Actually if we have multiple of binary vector, we can without loss of generality just work with the binary vector itself. If v is this binary vector, then cv after applying Ducci operation will be vector in form cw (we can pull out the c from all entries).

For example vector (1, 0) behaves exactly like (3, 0). In the first case we get (1,0) \rightarrow (1, 1) \rightarrow (0, 0) and in the second we get (3, 0) \rightarrow (3, 3) \rightarrow (0, 0) and every vector is just 3 times the respective vector in the first case.

After we prove all of this, we will try to concentrate more on length of a cycle. Informally said, cycle is a loop we get into. If we have (1,0,0) \rightarrow (1, 0, 1) \rightarrow (1, 1, 0) \rightarrow (0, 1, 1) \rightarrow (1, 0, 1), then we obtained cycle with length 4.

If we have binary vectors, we can view them as elements from module or vector space. We will need (and explain) knowledge about cosets, isomoprhism theorems and Cyclotomic polynomials

JoF EJK – debug and some code

Posted on by mathman

Last time we set our environment. Now let’s try to write some code and debug it.

The code is extremely vast and very often it is much easier to check how is something similar done rather than trying to think about the solution from scratch.

For example in JoF EJK client you can do /say %T% and it says time to chat.

Continue reading “JoF EJK – debug and some code” →

What exactly does processor to your code and reverse engineering

Posted on by mathman

Sometimes people ask me why is reverse engineering so hard. “But you have the files, why don’t you just somehow look in them?”

Well, you can “somehow” look in them, but that is the hard part. Let’s try it on example – we will write a code, generate exe and then we will try to go backwards.

We will write code in C, initializing two variables and then saving their sum to third variable.

The code:



int main()

{

  int a = 3;

  int b = 5;

  int c;

  c = a+b;

}

Okay, so more slowly – I told the language i want to have variables ‘a’ and ‘b’ with values 3 and 5. I want these numbers to be integers, so I wrote “int” before them. Then I want to have a variable ‘c’,  in which I save sum of ‘a’ and ‘b’.

All of this is in “main”, because that is the entry point of the program – if I did not put anything in main, the language would recognize it and assume I don’t want anything happening, so it would throw away anything I wrote about a, b and c.

But all of this is kinda “human readable” – why would your PC know what you mean by “int”, “main” or even equal sign?

To translate to “computer language”, we need instructions of how to move things in memory itself – we have a compiler for this. It reads the code we write and do “some magic” to it. After this magic we get an .exe file. 

Okay, cool, so we called our compiler on our code, it translates code to something else (yielding exe in process), computer understands and somewhere in processor value 3+5 was calculated. But how exactly?

________________________________________________________________

We can use a program to reverse engineer the process – meaning having only the .exe we can check the more instructions much more deeply. The problem is that we don’t get C code we wrote, but something much more complicated.

We get this:

Don’t panic, only few of the lines are relevant for our explanation. The not relevant parts do “something” to memory which we will just ignore here. All the lines are code in language called assembler. On the left side is instruction on the right side some value.
 

The part we are looking for is

mov [rbp+var_4], 3

mov [rbp+var_8], 5

mov edx, [rbp+var_4]

mov eax, [rbp+var_8]

add eax, edx

mov means move and add means… add. There are two explicit values, 3 and 5 – so compiler totally forgot the original names of our variables. They are moved around to some registers ending in edx and eax. And then instruction add adds values from register eax and edx and save the result to eax.

The exact term about what we did is “disassemble”, because we had resulting .exe and check the assembler code.

But we compiled our original code, is it possible to decompile, which would the original C code? Yes, it is possible, but often it does not really help.


It may have several reasons, compiler trying to optimize our code, allocating memory for variables in unexpected places, realizing variable c is never used, so it never uses it etc.   

This case was kinda easy (if one knows C and Assembler ofc), next time we will try something harder.