# Hyperimmunity ≈ Hypersimplicity. Algorithmic Complexities.

The notions of hyperimmune degrees have applications in computability theory, and in the study of its interaction with algorithmic randomness. There are several ways to define these notions, and lets concentrate on the concept of domination. A function g is dominated by a function f if g(n) ≤ f(n) for almost all n. It is sometimes technically useful to work with the following closely related concept: A function g is majorized by a function f if g(n) ≤ f(n) ∀ n.

A degree a is hyperimmune if there is a function f ≤T a that is not dominated by any computable function (or, equivalently, not majorized by any computable function). Otherwise, a is hyperimmune-free.

While 0 is clearly hyperimmune-free, all other ∆02 degrees are hyperimmune.

If a < b ≤ a′, then b is hyperimmune. In particular, every nonzero degree below 0′, and hence every nonzero degree, is hyperimmune.

We carry out the proof for the case a = 0. The general result follows by a straightforward relativization.

Let B be a set such that φ T φ’. we need to find a function g ≤B such that is not majorized by any computable function. Since B is ∆02, it has a computable approximation {Bs}s∈N. Define

g(n) = μs ≥ x (Bs ↾ n = B ↾ n)

g(n) is not the stage s by which the approximation to B ↾ n has stabilized, but rather the first stage s at which Bs ↾ n is correct. Clearly, g ≤B. Hypothesizing that no computable function majorizes g. Suppose h is computable and majorizes g. Hypothesizing on the addendum, B is computable as well. To compute B ↾ m, search for an n > m such that Bt ↾ m = Bn ↾ m ∀ t ∈ [n, h(n)]. Such an n must exist because there is a stage at which the approximation to B ↾ m stabilizes. By the definition of g and the choice of h, we have g(n) ∈ [n, h(n)], so B ↾ m = Bg(n) ↾ m = Bn ↾ m. Thus B is computable, which is a contradiction.

On the other hand, there do exist nonzero hyperimmune-free degrees.

We define a noncomputable set A of hyperimmune-free degree, using a technique known as forcing with computable perfect trees. A function tree is a function T: 2 → 2 such T(σ0) and T(σ1) are incompatible extensions of T(σ). For a tree T, let [T] be a collection of all X for which there is an infinite sequence β such that T(σ) ≺ X ∀ σ ≺ β. Building a sequence of {Ti}i∈N of computable trees such that [T0] ⊇ [T1] ⊇ [T2] ⊇ [T3]…since each [Ti] is closed, ∩n[Tn] ≠ 0. We will take A to be any element of this intersection.

The name “hyperimmune degree” comes from the notion of a hyperimmune set, which is a strong array that is a computable collection of disjoint finite sets {Fi}i∈N (which means not only that the Fi are uniformly computable, but that the function i ↦ max Fi is computable). A set A is hyperimmune if for all strong arrays {Fi}i∈N, there is an i such that Fi ⊂ Â. A set is hypersimple if its complement is hyperimmune.

Algorithmic Randomness and Complexity

# Imperfect Forward Secrecy – The Failure of Diffie-Hellman Key Exchange

Diffie-Hellman key exchange, also called exponential key exchange, is a method of digital encryption that uses numbers raised to specific powers to produce decryption keys on the basis of components that are never directly transmitted, making the task of a would-be code breaker mathematically overwhelming.

Let’s say Alice and Bob want to communicate with each other without John knowing what they’re saying or sending. Anything Alice sends to Bob, John will receive, likewise, anything Bob sends to Alice, John will also receive. So how do Alice and Bob send anything to each other without John understanding? Well that’s where Diffie-Hellman comes in.

To start, Alice and Bob decide publicly (John will also get a copy) on two prime numbers, g and n. Generally g is a small prime number and n is quite large, usually 2000 or more commonly 4000 bits long. So now Alice, Bob and John all know these numbers.

Now Alice decides secretly on another number, a. and Bob decides secretly on a number, b. Neither Alice nor Bob send these numbers, they are kept to themselves. Alice performs a calculation, g ^ a mod n, we’ll call this A, since it comes from a. Bob then performs g ^ b mod n which we’ll call B.

Alice sends Bob, A, and Bob sends Alice, B. Note John now has 4 numbers, A, B, g and n but not a or b. Finally, for the heart of the trick. Alice takes Bob’s and performs B ^ a mod n. Similarly, Bob takes Alice’s A and performs A ^ b mod n. This results in the same number i.e. B ^ a mod n = A ^ b mod n. They now have a shared number. Notice how John can’t figure out what these numbers are from the numbers he’s got.

Actually he can and its given a name called solving the discrete log problem. If we make n very large this becomes an extremely computationally heavy problem to solve and simply isn’t worth the time to figure out. John would have to figure out a or b from A or B which is simply far too time consuming.

So what can Alice and Bob do with this key they’ve just created together? Well they can use it to start encrypting messages they send to each other. A very simple example that should not be used anywhere as it’s extremely insecure is in encrypting their messages with a shift cipher (Caesar cipher) where the shift value is determined by the newly generated key. Both Alice and Bob can encrypt and decrypt the messages as they know the shift value but John can’t as he doesn’t have the key.

Diffie-Hellman key exchange is a cornerstone of applied cryptography, but it is often less secure than widely believed. The problems stem from the fact that the number field sieve for discrete log allows an attacker to perform a single precomputation that depends only on the group, after which computing individual logs in that group has a far lower cost. Although this fact is well known to cryptographers, it apparently has not been widely understood by system builders. Likewise, many cryptographers did not appreciate that the security of a large fraction of Internet communication depends on Diffie-Hellman key exchanges that use a few small, widely shared groups.

A key lesson from this state of affairs is that cryptographers and creators of practical systems need to work together more effectively. System builders should take responsibility for being aware of applicable cryptanalytic attacks. Cryptographers, for their part, should involve themselves in how crypto is actually being applied, such as through engagement with standards efforts and software review. Bridging the perilous gap that separates these communities will be essential for keeping future systems secure.

The Logjam attack: A man-in-the-middle can force TLS clients to use export-strength DH with any server that allows DHE_EXPORT. Then, by finding the 512-bit discrete log, the attacker can learn the session key and arbitrarily read or modify the contents. Datafs refers to False Start application data that some TLS clients send before receiving the server’s Finished message.

imperfect forward secrecy

# Why Can’t There Be Infinite Descending Chain Of Quotient Representations? – Part 3

For a quiver Q, the category Rep(Q) of finite-dimensional representations of Q is abelian. A morphism f : V → W in the category Rep(Q) defined by a collection of morphisms fi : Vi → Wi is injective (respectively surjective, an isomorphism) precisely if each of the linear maps fi is.

There is a collection of simple objects in Rep(Q). Indeed, each vertex i ∈ Q0 determines a simple object Si of Rep(Q), the unique representation of Q up to isomorphism for which dim(Vj) = δij. If Q has no directed cycles, then these so-called vertex simples are the only simple objects of Rep(Q), but this is not the case in general.

If Q is a quiver, then the category Rep(Q) has finite length.

Given a representation E of a quiver Q, then either E is simple, or there is a nontrivial short exact sequence

0 → A → E → B → 0

Now if B is not simple, then we can break it up into pieces. This process must halt, as every representation of Q consists of finite-dimensional vector spaces. In the end, we will have found a simple object S and a surjection f : E → S. Take E1 ⊂ E to be the kernel of f and repeat the argument with E1. In this way we get a filtration

… ⊂ E3 ⊂ E2 ⊂ E1 ⊂ E

with each quotient object Ei−1/Ei simple. Once again, this filtration cannot continue indefinitely, so after a finite number of steps we get En = 0. Renumbering by setting Ei := En−i for 1 ≤ i ≤ n gives a Jordan-Hölder filtration for E. The basic reason for finiteness is the assumption that all representations of Q are finite-dimensional. This means that there can be no infinite descending chains of subrepresentations or quotient representations, since a proper subrepresentation or quotient representation has strictly smaller dimension.

In many geometric and algebraic contexts, what is of interest in representations of a quiver Q are morphisms associated to the arrows that satisfy certain relations. Formally, a quiver with relations (Q, R) is a quiver Q together with a set R = {ri} of elements of its path algebra, where each ri is contained in the subspace A(Q)aibi of A(Q) spanned by all paths p starting at vertex aiand finishing at vertex bi. Elements of R are called relations. A representation of (Q, R) is a representation of Q, where additionally each relation ri is satisfied in the sense that the corresponding linear combination of homomorphisms from Vai to Vbi is zero. Representations of (Q, R) form an abelian category Rep(Q, R).

A special class of relations on quivers comes from the following construction, inspired by the physics of supersymmetric gauge theories. Given a quiver Q, the path algebra A(Q) is non-commutative in all but the simplest examples, and hence the sub-vector space [A(Q), A(Q)] generated by all commutators is non-trivial. The vector space quotientA(Q)/[A(Q), A(Q)] is seen to have a basis consisting of the cyclic paths anan−1 · · · a1 of Q, formed by composable arrows ai of Q with h(an) = t(a1), up to cyclic permutation of such paths. By definition, a superpotential for the quiver Q is an element W ∈ A(Q)/[A(Q), A(Q)] of this vector space, a linear combination of cyclic paths up to cyclic permutation.

# The Case of Morphisms of Representation Corresponding to A-Module Holomorphisms. Part 2

Representations of a quiver can be interpreted as modules over a non-commutative algebra A(Q) whose elements are linear combinations of paths in Q.

Let Q be a quiver. A non-trivial path in Q is a sequence of arrows am…a0 such that h(ai−1) = t(ai) for i = 1,…, m:

The path is p = am…a0. Writing t(p) = t(a0) and saying that p starts at t(a0) and, similarly, writing h(p) = h(am) and saying that p finishes at h(am). For each vertex i ∈ Q0, we denote by ei the trivial path which starts and finishes at i. Two paths p and q are compatible if t(p) = h(q) and, in this case, the composition pq can defined by juxtaposition of p and q. The length l(p) of a path is the number of arrows it contains; in particular, a trivial path has length zero.

The path algebra A(Q) of a quiver Q is the complex vector space with basis consisting of all paths in Q, equipped with the multiplication in which the product pq of paths p and q is defined to be the composition pq if t(p) = h(q), and 0 otherwise. Composition of paths is non-commutative; in most cases, if p and q can be composed one way, then they cannot be composed the other way, and even if they can, usually pq ≠ qp. Hence the path algebra is indeed non-commutative.

Let us define Al ⊂ A to be the subspace spanned by paths of length l. Then A = ⊕l≥0Al is a graded C-algebra. The subring A0 ⊂ A spanned by the trivial paths ei is a semisimple ring in which the elements ei are orthogonal idempotents, in other words eiej = ei when i = j, and 0 otherwise. The algebra A is finite-dimensional precisely if Q has no directed cycles.

The category of finite-dimensional representations of a quiver Q is isomorphic to the category of finitely generated left A(Q)-modules. Let (V, φ) be a representation of Q. We can then define a left module V over the algebra A = A(Q) as follows: as a vector space it is

V = ⊕i∈Q0 Vi

and the A-module structure is extended linearly from

eiv = v, v ∈ Mi

= 0, v ∈ Mj for j ≠ i

for i ∈ Qand

av = φa(vt(a)), v ∈ Vt(a)

= 0, v ∈ Vj for j ≠ t(a)

for a ∈ Q1. This construction can be inverted as follows: given a left A-module V, we set Vi = eiV for i ∈ Q0 and define the map φa: Vt(a) → Vh(a) by v ↦ a(v). Morphisms of representations of (Q, V) correspond to A-module homomorphisms.

# Indecomposable Objects – Part 1

An object X in a category C with an initial object is called indecomposable if X is not the initial object and X is not isomorphic to a coproduct of two noninitial objects. A group G is called indecomposable if it cannot be expressed as the internal direct product of two proper normal subgroups of G. This is equivalent to saying that G is not isomorphic to the direct product of two nontrivial groups.

A quiver Q is a directed graph, specified by a set of vertices Q0, a set of arrows Q1, and head and tail maps

h, t : Q1 → Q0

We always assume that Q is finite, i.e., the sets Q0 and Q1 are finite.

A (complex) representation of a quiver Q consists of complex vector spaces Vi for i ∈ Qand linear maps

φa : Vt(a) → Vh(a)

for a ∈ Q1. A morphism between such representations (V, φ) and (W, ψ) is a collection of linear maps fi : Vi → Wi for i ∈ Q0 such that the diagram

commutes ∀ a ∈ Q1. A representation of Q is finite-dimensional if each vector space Vi is. The dimension vector of such a representation is just the tuple of non-negative integers (dim Vi)i∈Q0.

Rep(Q) is the category of finite-dimensional representations of Q. This category is additive; we can add morphisms by adding the corresponding linear maps fi, the trivial representation in which each Vi = 0 is a zero object, and the direct sum of two representations is obtained by taking the direct sums of the vector spaces associated to each vertex. If Q is the one-arrow quiver, • → •, then the classification of indecomposable objects of Rep(Q), yields the objects E ∈ Rep(Q) which do not have a non-trivial direct sum decomposition E = A ⊕ B. An object of Rep(Q) is just a linear map of finite-dimensional vector spaces f: V1 → V2. If W = im(f) is a nonzero proper subspace of V2, then the splitting V2 = U ⊕ W, and the corresponding object of Rep(Q) splits as a direct sum of the two representations

V1 →ƒ W and 0 → W

Thus if an object f: V1 → V2 of Rep(Q) is indecomposable, the map f must be surjective. Similarly, if ƒ is nonzero, then it must also be injective. Continuing in this way, one sees that Rep(Q) has exactly three indecomposable objects up to isomorphism:

C → 0, 0 → C, C →id C

Every other object of Rep(Q) is a direct sum of copies of these basic representations.

# Lie-Dragging Sections Vectorially. Thought of the Day 149.0

Generalized vector fields over a bundle are not vector fields on the bundle in the standard sense; nevertheless, one can drag sections along them and thence define their Lie derivative. The formal Lie derivative on a bundle may be seen as a generalized vector field. Furthermore, generalized vector fields are objects suitable to describe generalized symmetries.

Let B = (B, M, π; F) be a bundle, with local fibered coordinates (xμ; yi). Let us consider the pull-back of the tangent bundle  τB: TB → B along the map πk0: JkB → B:

A generalized vector field of order k over B is a section Ξ of the fibre bundle π: πk*TB → JkB, i.e.

for each section σ: M → B, one can define Ξσ = i ○ Ξ ○ jkσ: M → TB, which is a vector field over the section σ. Generalized vector fields of order k = 0 are ordinary vector fields over B. Locally, Ξ(xμ, yi, …, yiμ1,…μk) is given the form:

Ξ = ξμ(xμ, yi, …, yiμ1,…μk)∂μ + ξi(xμ, yi, …, yiμ1,…μk)∂i

which, for k ≠ 0, is not an ordinary vector field on B due to the dependence of the components (ξμ, ξi) on the derivative of fields. Once one computes it on a section σ, then the pulled-back components depend just on the basic coordinates (xμ) so that Ξσ is a vector field over the section σ, in the standard sense. Thus, generalized vector fields over B do not preserve the fiber structure of B.

A generalized projectable vector field of order k over the bundle B is a generalized vector field Ξ over B which projects on to an ordinary vector field ξ = ξμ(x)∂μ on the base. Locally, a generalized projectable vector field over B is in the form:

Ξ = ξμ(xμ)∂μ + ξi(xμ, yi, …, yiμ1,…μk)∂i

As a particular case, one can define generalized vertical vector fields (of order k) over B, which are locally of the form:

Ξ = ξi(xμ, yi, …, yiμ1,…μk)∂i

In particular, for any section σ of B and any generalized vertical vector field Ξ over B, one can define a vertical vector field over σ given by:

Ξσ = ξi(xμ, σi(x),…, ∂μ1,…, μkσi(x))∂i

If Ξ = ξμμ + ξii is a generalized projectable vector field, then Ξ(v) = (ξi – yiμξμ)∂i = ξi(v)i is a generalized vertical vector field, where Ξ(v) is called the vertical part of Ξ.

If σ’: ℜ x M → B is a smooth map such that for any fixed s ∈ ℜ σs(x) = σ'(s, x): M → B is a global section of B. The map σ’ as well as the family {σs}, is then called a 1-parameter family of sections. In other words, a suitable restriction of the family σs, is a homotopic deformation with s ∈ ℜ of the central section σ = σ0. Often one restricts it to a finite (open) interval, conventionally (- 1, 1) (or (-ε, ε) if “small” deformations are considered). Analogous definitions are given for the homotopic families of sections over a fixed open subset U ⊆ M or on some domain D ⊂ M (possibly with values fixed at the boundary ∂D, together with any number of their derivatives).

A 1-parameter family of sections σs is Lie-dragged along a generalized projectable vector field Ξ iff

(v))σs = d/ds σs

thus dragging the section.

# Symmetrical – Asymmetrical Dialectics Within Catastrophical Dynamics. Thought of the Day 148.0

Catastrophe theory has been developed as a deterministic theory for systems that may respond to continuous changes in control variables by a discontinuous change from one equilibrium state to another. A key idea is that system under study is driven towards an equilibrium state. The behavior of the dynamical systems under study is completely determined by a so-called potential function, which depends on behavioral and control variables. The behavioral, or state variable describes the state of the system, while control variables determine the behavior of the system. The dynamics under catastrophe models can become extremely complex, and according to the classification theory of Thom, there are seven different families based on the number of control and dependent variables.

Let us suppose that the process yt evolves over t = 1,…, T as

dyt = -dV(yt; α, β)dt/dyt —– (1)

where V (yt; α, β) is the potential function describing the dynamics of the state variable ycontrolled by parameters α and β determining the system. When the right-hand side of (1) equals zero, −dV (yt; α, β)/dyt = 0, the system is in equilibrium. If the system is at a non-equilibrium point, it will move back to its equilibrium where the potential function takes the minimum values with respect to yt. While the concept of potential function is very general, i.e. it can be quadratic yielding equilibrium of a simple flat response surface, one of the most applied potential functions in behavioral sciences, a cusp potential function is defined as

−V(yt; α, β) = −1/4yt4 + 1/2βyt2 + αyt —– (2)

with equilibria at

-dV(yt; α, β)dt/dyt = -yt3 + βyt + α —– (3)

being equal to zero. The two dimensions of the control space, α and β, further depend on realizations from i = 1 . . . , n independent variables xi,t. Thus it is convenient to think about them as functions

αx = α01x1,t +…+ αnxn,t —– (4)

βx = β0 + β1x1,t +…+ βnxn,t —– (5)

The control functions αx and βx are called normal and splitting factors, or asymmetry and bifurcation factors, respectively and they determine the predicted values of yt given xi,t. This means that for each combination of values of independent variables there might be up to three predicted values of the state variable given by roots of

-dV(yt; αx, βx)dt/dyt = -yt3 + βyt + α = 0 —– (6)

This equation has one solution if

δx = 1/4αx2 − 1/27βx3 —– (7)

is greater than zero, δx > 0 and three solutions if δx < 0. This construction can serve as a statistic for bimodality, one of the catastrophe flags. The set of values for which the discriminant is equal to zero, δx = 0 is the bifurcation set which determines the set of singularity points in the system. In the case of three roots, the central root is called an “anti-prediction” and is least probable state of the system. Inside the bifurcation, when δx < 0, the surface predicts two possible values of the state variable which means that the state variable is bimodal in this case.

Most of the systems in behavioral sciences are subject to noise stemming from measurement errors or inherent stochastic nature of the system under study. Thus for a real-world applications, it is necessary to add non-deterministic behavior into the system. As catastrophe theory has primarily been developed to describe deterministic systems, it may not be obvious how to extend the theory to stochastic systems. An important bridge has been provided by the Itô stochastic differential equations to establish a link between the potential function of a deterministic catastrophe system and the stationary probability density function of the corresponding stochastic process. Adding a stochastic Gaussian white noise term to the system

dyt = -dV(yt; αx, βx)dt/dyt + σytdWt —– (8)

where -dV(yt; αx, βx)dt/dyt is the deterministic term, or drift function representing the equilibrium state of the cusp catastrophe, σyt is the diffusion function and Wt is a Wiener process. When the diffusion function is constant, σyt = σ, and the current measurement scale is not to be nonlinearly transformed, the stochastic potential function is proportional to deterministic potential function and probability distribution function corresponding to the solution from (8) converges to a probability distribution function of a limiting stationary stochastic process as dynamics of yt are assumed to be much faster than changes in xi,t. The probability density that describes the distribution of the system’s states at any t is then

fs(y|x) = ψ exp((−1/4)y4 + (βx/2)y2 + αxy)/σ —– (9)

The constant ψ normalizes the probability distribution function so its integral over the entire range equals to one. As bifurcation factor βx changes from negative to positive, the fs(y|x) changes its shape from unimodal to bimodal. On the other hand, αx causes asymmetry in fs(y|x).