On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

On Tensor Products of Simple Modules for Simple Groups

In an attempt to get some information on the multiplicative structure of the Green ring we study algebraic modules for simple groups, and associated groups such as quasisimple and almost-simple groups. We prove that, for almost all groups of Lie type in defining characteristic, the natural module is non-algebraic. For alternating and symmetric groups, we prove that the simple modules in p-blocks with defect groups of order p ² are algebraic, for p?≤?5. Finally, we analyze nine sporadic groups, finding that all simple modules are algebraic for various primes and sporadic groups.     

On the homogeneous algebraic graphs of large girth and their applications

Families of finite graphs of large girth were introduced in classical extremal graph theory. One important theoretical result here is the upper bound on the maximal size of the graph with girth ?2d established in Even Circuit Theorem by P. Erdös. We consider some results on such algebraic graphs over any field. The upper bound on the dimension of variety of edges for algebraic graphs of girth ?2d is established. Getting the lower bound, we use the family of bipartite graphs D(n,K) with n?2 over a field K, whose partition sets are two copies of the vector space Kⁿ. We consider the problem of constructing homogeneous algebraic graphs with a prescribed girth and formulate some problems motivated by classical extremal graph theory. Finally, we present a very short survey on applications of finite homogeneous algebraic graphs to coding theory and cryptography.     

The PRV-formula for tensor product decompositions and its applications

Let G be a semisimple algebraic group, V a simple finite-dimensional self-dual G-module, and W an arbitrary simple finite-dimensional G-module. Using the triple multiplicity formula due to Parthasarathy, Ranga Rao, and Varadarajan, we describe the multiplicities of W in the symmetric and exterior squares of V in terms of the action of a maximum-length element of the Weyl group on some subspace in V ^T , where T ? G is a maximal torus. By way of application, we consider the cases in which V is the adjoint, little adjoint, or, more generally, a small G-module. We also obtain a general upper bound for triple multiplicities in terms of Kostant’s partition function.     

Algebraic Independence of Solutions of First-Order Rational Difference Equations

We prove a theorem on algebraic independence of solutions of first order rational difference equations. By the theorem, we are able to prove algebraic independence of x, the exponential function e ^x and the Weierstrass function ${\wp(x)}$ over ${\mathbb{C}}$ only by seeing degrees of polynomials associated with their double angle formulas. As a corollary, we obtain a result on unsolvability of a first-order rational difference equation by solutions of other first-order rational difference equations, which implies its irreducibility. Additionally, we introduce some applications to algebraic independence of functions f(x), f(x ²), . . . , f(x ⁿ ).     

Graded Associative Conformal Algebras of Finite Type

In this paper, we consider graded associative conformal algebras. The class of these objects includes pseudo-algebras over non-cocommutative Hopf algebras of regular functions on some linear algebraic groups. In particular, an associative conformal algebra which is graded by a finite group Γ is a pseudo-algebra over the coordinate Hopf algebra of a linear algebraic group G such that the identity component G ⁰ is the affine line and G/G ⁰???Γ. A classification of simple and semisimple graded associative conformal algebras of finite type is obtained.     

On some probabilistic approximations for AES-like s-boxes

Several recently proposed block ciphers such as AES, Camellia, Shark, Square and Hierocrypt use s-boxes that are based on the inversion mapping over GF(2ⁿ). In order to hide the simple algebraic structure in this mapping, an affine transformation over F₂ is usually used after the output of the s-box. In some ciphers, an additional affine transformation is used before the input of the s-box as well. In this paper, we study the algebraic properties of a simple approximation in the form s(x)=ax^-1+b, a,b∈GF(2ⁿ) for such s-boxes. The implication of this result on the cryptanalysis of these ciphers remains an open problem.     

π and the hypergeometric functions of complex argument

Text

In this article we derive some new identities concerning π, algebraic radicals and some special occurrences of the Gauss hypergeometric function ₂F₁ in the analytic continuation. All of them have been derived by tackling some elliptic or hyperelliptic known integral, and looking for another representation of it by means of hypergeometric functions like those of Gauss, Appell or Lauricella. In any case we have focused on integrand functions having at least one couple of complex-conjugate roots. Founding upon a special hyperelliptic reduction formula due to Hermite (1876) [6], π is obtained as a ratio of a complete elliptic integral and the four-variable Lauricella function. Furthermore, starting with a certain binomial integral, we succeed in providing as a ratio of a linear combination of complete elliptic integrals of the first and second kinds to the Appell hypergeometric function of two complex-conjugate arguments. Each of the formulae we found theoretically has been satisfactorily tested by means of Mathematica^®.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=rQqtVtAf-RQ.     

Additive Hilbert's Theorem 90 in the ring of algebraic integers

For a number field K, we give a complete characterization of algebraic numbers which can be expressed by a difference of two K-conjugate algebraic integers. These turn out to be the algebraic integers whose Galois group contains an element, acting as a cycle on some collection of conjugates which sum to zero. Hence there are no algebraic integers which can be written as a difference of two conjugate algebraic numbers but cannot be written as a difference of two conjugate algebraic integers. A generalization of the construction to a commutative ring is also given. Furthermore, we show that for n ?_ 3 there exist algebraic integers which can be written as a linear form in n K-conjugate algebraic numbers but cannot be written by the same linear form in K-conjugate algebraic integers.     

Optimal concavity of some Hessian operators and the prescribed σ 2 curvature measure problem

In this paper, we consider a minimal value problem and obtain an algebraic inequality. As an application, we obtain the optimal concavity of some Hessian operators and then establish the C2 a priori estimate for a class of prescribed σ2 curvature measure equations.     

Existence and decay of solutions in full space to Navier-Stokes equations with delays

We consider the Navier-Stokes equations with delays in Rⁿ,2≤n≤4. We prove existence of weak solutions when the external forces contain some hereditary characteristics and uniqueness when n=2. Moreover, if the external forces satisfy a time decay condition we show that the solution decays at an algebraic rate.     

Moduli of objects in dg-categories

The purpose of this work is to prove the existence of an algebraic moduli classifying objects in a given triangulated category.To any dg-category T (over some base ring k), we define a D⁻-stack MT in the sense of [Toën B., Vezzosi G., Homotopical algebraic geometry II: Geometric stacks and applications, Mem. Amer. Math. Soc., in press], classifying certain Top-dg-modules. When T is saturated, MT classifies compact objects in the triangulated category [T] associated to T. The main result of this work states that under certain finiteness conditions on T (e.g. if it is saturated) the D⁻-stack MT is locally geometric (i.e. union of open and geometric sub-stacks). As a consequence we prove the algebraicity of the group of auto-equivalences of saturated dg-categories. We also obtain the existence of reasonable moduli for perfect complexes on a smooth and proper scheme, as well as complexes of representations of a finite quiver.     

Noncommutative localization in algebraic L-theory

Given a noncommutative (Cohn) localization A→σ⁻¹A which is injective and stably flat we obtain a lifting theorem for induced f.g. projective σ⁻¹A-module chain complexes and localization exact sequences in algebraic L-theory, matching the algebraic K-theory localization exact sequence of Neeman-Ranicki [Amnon Neeman, Andrew Ranicki, Noncommutative localisation in algebraic K-theory I, Geom. Topol. 8 (2004) 1385-1425] and Neeman [Amnon Neeman, Noncommutative localisation in algebraic K-theory II, Adv. Math. 213 (2007) 785-819].     

Sum of graphs of continuous functions and boundedness of additive operators

Assume that and are uniformly continuous functions, where D₁,D₂⊂X are nonempty open and arc-connected subsets of a real normed space X. We prove that then either f and g are affine functions, that is f(x)=x^∗(x)+a and g(x)=x^∗(x)+b with some x^∗∈X^∗ and a,b∈R or the algebraic sum of graphs of functions f and g has a nonempty interior in a product space X×R treated as a normed space with a norm .     

Monoidal intervals of clones on infinite sets

Let X be an infinite set of cardinality κ. We show that if L is an algebraic and dually algebraic distributive lattice with at most 2^κ completely join irreducibles, then there exists a monoidal interval in the clone lattice on X which is isomorphic to the lattice 1+L obtained by adding a new smallest element to L. In particular, we find that if L is any chain which is an algebraic lattice, and if L does not have more than 2^κ completely join irreducibles, then 1+L appears as a monoidal interval; also, if λ?2^κ, then the power set of λ with an additional smallest element is a monoidal interval. Concerning cardinalities of monoidal intervals these results imply that there are monoidal intervals of all cardinalities not greater than 2^κ, as well as monoidal intervals of cardinality 2^λ, for all λ?2^κ.     

Order-convergence and iterative interval methods

In the first part of this paper we introduce order-convergence in partially ordered spaces having lattice properties. Lipschitz assumptions are made for an operator equation Tx = Θ, and additional operators are then derived from the Lipschitz operators. We show how to solve the operator equation by means of these operators, using iterative methods which produce interval sequences, and we state some theorems on the inclusion and the existence of a solution of the equation as well as on the convergence of the interval sequences. In the second part of the paper we show how these theorems can be used to find the solution of a real equation, a nonlinear system of equations in $\text{R}$ⁿ and an algebraic eigenvalue problem.     

The Nöther and Riemann-Roch type theorems for piecewise algebraic curve

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function. In this paper, the Nöther type theorems for C ^µ piecewise algebraic curves are obtained. The theory of the linear series of sets of places on the piecewise algebraic curve is also established. In this theory, singular cycles are put into the linear series, and a complete series of the piecewise algebraic curves consists of all effective ordinary cycles in an equivalence class and all effective singular cycles which are equivalent specifically to any effective ordinary cycle in the equivalence class. This theory is a generalization of that of linear series of the algebraic curve. With this theory and the fundamental theory of multivariate splines on smoothing cofactors and global conformality conditions, and the results on the general expression of multivariate splines, we get a formula on the index, the order and the dimension of a complete series of the irreducible C ^µ piecewise algebraic curves and the degree, the genus and the smoothness of the curves, hence the Riemann-Roch type theorem of the C ^µ piecewise algebraic curve is established.     

Locally compact multivector extensions

The aim of this paper is to develop a locally compact extension of an arbitrary normed space in such a way that the initial algebraic structure is prolonged in some sense. To obtain such an extension, we weaken vector space axioms allowing a set-valued addition and introduce in this scheme a topological structure, by means of a hypertopology, and a compatible proximity. Finally, the locally compact multivector extension appears as an ultrafilter space. We also provide a Young measure related interpretation of these extensions when the normed space is an L^p space.     

Algebraic signatures of convex and non-convex codes

A convex code is a binary code generated by the pattern of intersections of a collection of open convex sets in some Euclidean space. Convex codes are relevant to neuroscience as they arise from the activity of neurons that have convex receptive fields. In this paper, we develop algebraic methods to determine if a code is convex. Specifically, we use the neural ideal of a code, which is a generalization of the Stanley–Reisner ideal. Using the neural ideal together with its standard generating set, the canonical form, we provide algebraic signatures of certain families of codes that are non-convex. We connect these signatures to the precise conditions on the arrangement of sets that prevent the codes from being convex. Finally, we also provide algebraic signatures for some families of codes that are convex, including the class of intersection-complete codes. These results allow us to detect convexity and non-convexity in a variety of situations, and point to some interesting open questions.