Hyperimmunity ≈ Hypersimplicity. Algorithmic Complexities.

1*aXW_00lLrZn0_V4ytKoQUw

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

Advertisements

Network Theoretic of the Fermionic Quantum State – Epistemological Rumination. Thought of the Day 150.0

galitski_moatv3

In quantum physics, fundamental particles are believed to be of two types: fermions or bosons, depending on the value of their spin (an intrinsic ‘angular moment’ of the particle). Fermions have half-integer spin and cannot occupy a quantum state (a configuration with specified microscopic degrees of freedom, or quantum numbers) that is already occupied. In other words, at most one fermion at a time can occupy one quantum state. The resulting probability that a quantum state is occupied is known as the Fermi-Dirac statistics.

Now, if we want to convert this into a model with maximum entropy, where the real movement is defined topologically, then we require a reproduction of heterogeneity that is observed. The starting recourse is network theory with an ensemble of networks where each vertex i has the same degree ki as in the real network. This choice is justified by the fact that, being an entirely local topological property, the degree is expected to be directly affected by some intrinsic (non-topological) property of vertices. The caveat is that the real shouldn’t be compared with the randomized, which could otherwise lead to interpreting the observed as ‘unavoidable’ topological constraints, in the sense that the violation of the observed values would lead to an ‘impossible’, or at least very unrealistic values.

The resulting model is known as the Configuration Model, and is defined as a maximum-entropy ensemble of graphs with given degree sequence. The degree sequence, which is the constraint defining the model, is nothing but the ordered vector k of degrees of all vertices (where the ith component ki is the degree of vertex i). The ordering preserves the ‘identity’ of vertices: in the resulting network ensemble, the expected degree ⟨ki⟩ of each vertex i is the same as the empirical value ki for that vertex. In the Configuration Model, the graph probability is given by

P(A) = ∏i<jqij(aij) =  ∏i<jpijaij (1 – pij)1-aij —– (1)

where qij(a) = pija (1 – pij)1-a is the probability that particular entry of the adjacency matrix A takes the value aij = a, which is a Bernoulli process with different pairs of vertices characterized by different connection probabilities pij. A Bernoulli trial (or Bernoulli process) is the simplest random event, i.e. one characterized by only two possible outcomes. One of the two outcomes is referred to as the ‘success’ and is assigned a probability p. The other outcome is referred to as the ‘failure’, and is assigned the complementary probability 1 − p. These probabilities read

⟨aij⟩ = pij = (xixj)/(1 + xixj) —– (2)

where xi is the Lagrange multiplier obtained by ensuring that the expected degree of the corresponding vertex i equals its observed value: ⟨ki⟩ = ki ∀ i. As always happens in maximum-entropy ensembles, the probabilistic nature of configurations implies that the constraints are valid only on average (the angular brackets indicate an average over the ensemble of realizable networks). Also note that pij is a monotonically increasing function of xi and xj. This implies that ⟨ki⟩ is a monotonically increasing function of xi. An important consequence is that two variables i and j with the same degree ki = kj must have the same value xi = xj.

Unknown

(2) provides an interesting connection with quantum physics, and in particular the statistical mechanics of fermions. The ‘selection rules’ of fermions dictate that only one particle at a time can occupy a single-particle state, exactly as each pair of vertices in binary networks can be either connected or disconnected. In this analogy, every pair i, j of vertices is a ‘quantum state’ identified by the ‘quantum numbers’ i and j. So each link of a binary network is like a fermion that can be in one of the available states, provided that no two objects are in the same state. (2) indicates the expected number of particles/links in the state specified by i and j. With no surprise, it has the same form of the so-called Fermi-Dirac statistics describing the expected number of fermions in a given quantum state. The probabilistic nature of links allows also for the presence of empty states, whose occurrence is now regulated by the probability coefficients (1 − pij). The Configuration Model allows the whole degree sequence of the observed network to be preserved (on average), while randomizing other (unconstrained) network properties. now, when one compares the higher-order (unconstrained) observed topological properties with their expected values calculated over the maximum-entropy ensemble, it should be indicative of the fact that the degree of sequence is informative in explaining the rest of the topology, which is a consequent via probabilities in (2). Colliding these into a scatter plot, the agreement between model and observations can be simply assessed as follows: the less scattered the cloud of points around the identity function, the better the agreement between model and reality. In principle, a broadly scattered cloud around the identity function would indicate the little effectiveness of the chosen constraints in reproducing the unconstrained properties, signaling the presence of genuine higher-order patterns of self-organization, not simply explainable in terms of the degree sequence alone. Thus, the ‘fermionic’ character of the binary model is the mere result of the restriction that no two binary links can be placed between any two vertices, leading to a mathematical result which is formally equivalent to the one of quantum statistics.

Skeletal of the Presentation on AIIB and Blue Economy in Mumbai during the Peoples’ Convention on 22nd June 2018

Main features in AIIB Financing

  1. investments in regional members
  2. supports longer tenors and appropriate grace period
  3. mobilize funding through insurance, banks, funds and sovereign wealth (like the China Investment Corporation (CIC) in the case of China)
  4. funds on economic/financial considerations and on project benefits, eg. global climate, energy security, productivity improvement etc.

Public Sector:

  1. sovereign-backed financing (sovereign guarantee)
  2. loan/guarantee

Private Sector:

  1. non-sovereign-backed financing (private sector, State Owned Enterprises (SOEs), sub-sovereign and municipalities)
  2. loans and equity
  3. bonds, credit enhancement, funds etc.

—— portfolio is expected to grow steadily with increasing share of standalone projects from 27% in 2016 to 39% in 2017 and 42% in 2018 (projected)

—— share of non-sovereign-backed projects has increased from 1% in 2016 to 36% of portfolio in 2017. share of non-sovereign-backed projects is projected to account for about 30% in 2018

Untitled

Why would AIIB be interested in the Blue Economy?

  1. To appropriate (expropriate) the potential of hinterlands
  2. increasing industrialization
  3. increasing GDP
  4. increasing trade
  5. infrastructure development
  6. Energy and Minerals in order to bring about a changing landscape
  7. Container: regional collaboration and competition

AIIB wishes to change the landscape of infrastructure funding across its partner countries, laying emphasis on cross-country and cross-sectoral investments in the shipping sector — Yee Ean Pang, Director General, Investment Operations, AIIB.

He also opined that in the shipping sector there is a need for private players to step in, with 40-45 per cent of stake in partnership being offered to private players.

Untitled

Projects aligned with Sagarmala are being considered for financial assistance by the Ministry of Shipping under two main headings:

1. Budgetary Allocations from the Ministry of Shipping

    a. up to 50% of the project cost in the form of budgetary grant

    b. Projects having high social impact but low/no Internal Rate of Return (IRR) may be provided funding, in convergence with schemes of other central line ministries. IRR is a metric used in capital budgeting to estimate the profitability of potential investments. It is a discount rate that makes the net present value (NPV) of all cash flows from a particular project equal to zero. NPV is the difference between the present value of cash inflows and present value of cash outflows over a period of time. IRR is sometimes referred to as “economic rate of return” or “discounted cash flow rate of return.” The use of “internal” refers to the omission of external factors, such as the cost of capital or inflation, from the calculation.

2. Funding in the form of equity by Sagarmala Development Co. Ltd.

    a. SDCL to provide 49% equity funding to residual projects

    b. monitoring is to be jointly done by SDCL and implementing agency at the SPV level

    c.  project proponent to bear operation and maintenance costs of the project

     i. importantly, expenses incurred for project development to be treated as part of SDCL’s equity contribution

     ii. preferences to be given to projects where land is being contributed by the project proponent

What are the main financing issues?

  1. Role of MDBs and BDBs for promotion of shipping sector in the country
  2. provision of long-term low-cost loans to shipping companies for procurement of vessels
  3. PPPs (coastal employment zones, port connectivity projects), EPCs, ECBs (port expansion and new port development), FDI in Make in India 2.0 of which shipping is a major sector identified, and conventional bank financing for port modernization and port connectivity

the major constraining factors, however, are:

  1. uncertainty in the shipping sector, cyclical business nature
  2. immature financial markets

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.

Untitled

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

 

8cmbD

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

1-s2.0-S0001870811003495-fx003

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:

Untitled

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.

Untitled

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

Untitled

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.