Some lower bounds on the algebraic immunity of functions given by their trace forms

The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2 ⁿ ), as well as for larger classes of functions defined by their trace forms. In particular, for n ≥ 5, the algebraic immunity of the function Tr _n (x ^?1) has a lower bound ?2√n + 4? ? 4, which is close enough to the previously obtained upper bound ?√n? + ?n/?√n?? ? 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree ≤ d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.     

On polynomial solutions of the linear stationary control system

It is known that the controllable system x′ = Bx + Du, where the x is the n-dimensional vector, can be transferred from an arbitrary initial state x(0) = x ⁰ to an arbitrary finite state x(T) = x ^T by the control function u(t) in the form of the polynomial in degrees t. In this work, the minimum degree of the polynomial is revised: it is equal to 2p + 1, where the number (p ? 1) is a minimum number of matrices in the controllability matrix (Kalman criterion), whose rank is equal to n. A simpler and a more natural algorithm is obtained, which first brings to the discovery of coefficients of a certain polynomial from the system of algebraic equations with the Wronskian and then, with the aid of differentiation, to the construction of functions of state and control.     

Generalized Preparata codes and 2-resolvable Steiner quadruple systems

We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce 2-resolvable Steiner quadruple systems S(n, 4, 3) (i.e., systems S(n, 4, 3) that can be partitioned into disjoint Steiner systems S(n, 4, 2)). The obtained partitions of systems S(n, 4, 3) into systems S(n, 4, 2) are not equivalent to such partitions previously known.     

Finding Coefficients of the Full Array of Motion-Independent <Emphasis Type="Italic">N</Emphasis>-Body Potentials of Metric Gravity from Gravity’s Exterior and Interior Effacement Algebra

In the author’s previous publications, a recursive linear algebraic method was introduced for obtaining (without gravitational radiation) the full potential expansions for the gravitational metric field components and the Lagrangian for a general N-body system. Two apparent properties of gravity— Exterior Effacement and Interior Effacement—were defined and fully enforced to obtain the recursive algebra, especially for the motion-independent potential expansions of the general N-body situation. The linear algebraic equations of this method determine the potential coefficients at any order n of the expansions in terms of the lower-order coefficients. Then, enforcing Exterior and Interior Effacement on a selecedt few potential series of the full motion-independent potential expansions, the complete exterior metric field for a single, spherically-symmetric mass source was obtained, producing the Schwarzschild metric field of general relativity. In this fourth paper of this series, the complete spatial metric’s motion-independent potentials for N bodies are obtained using enforcement of Interior Effacement and knowledge of the Schwarzschild potentials. From the full spatial metric, the complete set of temporal metric potentials and Lagrangian potentials in the motion-independent case can then be found by transfer equations among the coefficients κ(n, α) → λ(n, ε) → ξ(n, α) with κ(n, α), λ(n, ε), ξ(n, α) being the numerical coefficients in the spatial metric, the Lagrangian, and the temporal metric potential expansions, respectively.     

Relations between Transition Rates and Quantum Numbers in Gravitational Potentials

This paper forms part of an ongoing investigation to examine the quantum prediction that isolated baryons and electrons in the deep gravity wells of galaxy halos should exhibit reduced interaction cross-sections by virtue of the composition of the gravitational eigenspectra of their wave functions, and thereby identify a possible mechanism responsible for the origin of dark matter, without resorting to new physics or unknown particles. Relevant to this investigation are the electromagnetic state-to-state transition rates of charged particles occupying these gravitational eigenstates (EinsteinA coefficients), and, in the present work, we examine trends in these rates and net state lifetimes for particles in 1/r potential wells for values of the principal quantum number n and the angular momentum quantum number l. We find that transition rates decrease with increasing n and l, and that the rate is more steeply dependent on l when the quantum parameter Δp (≡ Δn ? Δl) is greater, in agreement with earlier work. It is also found that there is an empirical relationship between the total state lifetime τ and the eigenvalues n and l, which is given by τ ∝ n ^α l ^β , where α ≈ 3 and β ≈ 2. The results apply equally to electrical potential wells, where the phenomena of reduced cross-sections and long radiative lifetimes is well known in the case of the Rydberg states of electrons in atoms. More importantly, in the case of gravitational eigenstates discussed here, the quantum prediction of low Einstein A (and therefore B) coefficients ofmany of the stateto-state transitions will mean that a particle whose eigenspectral composition consists of many of these weakly interacting states will be less likely to undergo scattering processes such as Compton scattering. Trends in the Einstein coefficients over the range of component eigenstates are required for calculating the net visibility and interaction rates of the generalized wave functions representing charged particles in macroscopic gravitational fields.     

Higher-order polynomial approximation

A new approach to polynomial higher-order approximation (smoothing) based on the basic elements method (BEM) is proposed. A BEM polynomial of degree n is defined by four basic elements specified on a three-point grid: x ₀ + α < x ₀ < x ₀ + β, αβ <0. Formulas for the calculation of coefficients of the polynomial model of order 12 were derived. These formulas depend on the interval length, continuous parameters α and β, and the values of f ^(m)(x ₀+ν), ν = α, β, 0, m = 0,3. The application of higher-degree BEM polynomials in piecewise-polynomial approximation and smoothing improves the stability and accuracy of calculations when the grid step is increased and reduces the computational complexity of the algorithms.     

A real QZ algorithm for structured companion pencils

We design a fast implicit real QZ algorithm for eigenvalue computation of structured companion pencils arising from linearizations of polynomial rootfinding problems. The modified QZ algorithm computes the generalized eigenvalues of an \(N\times N\) structured matrix pencil using O(N) flops per iteration and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

On kernel engineering via Paley–Wiener

A radial basis function approximation takes the form

$s(x)=\sum_{k=1}^na_k\phi(x-b_k),\quad x\in {\mathbb{R}}^d,$

where the coefficients a ₁,…,a _n are real numbers, the centres b ₁,…,b _n are distinct points in ? ^d , and the function φ:? ^d →? is radially symmetric. Such functions are highly useful in practice and enjoy many beautiful theoretical properties. In particular, much work has been devoted to the polyharmonic radial basis functions, for which φ is the fundamental solution of some iterate of the Laplacian. In this note, we consider the construction of a rotation-invariant signed (Borel) measure μ for which the convolution ψ=μ φ is a function of compact support, and when φ is polyharmonic. The novelty of this construction is its use of the Paley–Wiener theorem to identify compact support via analysis of the Fourier transform of the new kernel ψ, so providing a new form of kernel engineering.

     

On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems

A function is introduced that characterizes the complexity of postoptimality analysis of discrete optimization problems. For this function, the upper O(2^poly(n)) and lower \( \Omega \left( {\frac{{{2^n}}}{{\sqrt {{n + 1}} }}} \right) \) 2 bounds are obtained in the class of branch and bound methods for the knapsack problem. A class of set covering problems with a polynomial estimate of this function is observed     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Organization of self-diagnosis of the discrete multicomponent systems a structure like bipartite quasicomplete graphs

Organization of an efficient self-diagnosis of the multicomponent computer and communication systems of diverse structures always attracted attention of the researchers and engineers. A method to solve these problems is presented in the paper by way of the example of a system whose structure is modeled by a uniform ordinary bipartite graph of diameter d = 3, any degree s > 1, and any number n of vertices, where n = s(s ? 1) + 1. The method requires checking of (s ? 1)³ graph loops of length eight each, which is smaller than the number s ²(s ? 1) + s of checks of single graph edges.     

On (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis> )-Distance Anti-Magic and 1-Vertex Bimagic Vertex Labelings of Certain Types of Graphs

The results for the corona P _n ?°?P₁ are generalized, which make it possible to state that P _n ?°?P₁ is not an ( a, d)-distance antimagic graph for arbitrary values of a and d. A condition for the existence of an ( a, d)-distance antimagic labeling of a hypercube Q _n is obtained. Functional dependencies are found that generate this type of labeling for Q _n . It is proved by the method of mathematical induction that Q _n is a (2 ⁿ ?+?n???1,?n???2) -distance antimagic graph. Three types of graphs are defined that do not allow a 1-vertex bimagic vertex labeling. A relation between a distance magic labeling of a regular graph G and a 1-vertex bimagic vertex labeling of G?∪?G is established.     

Local indistinguishability of multipartite orthogonal product bases

So far, very little is known about local indistinguishability of multipartite orthogonal product bases except some special cases. We first give a method to construct an orthogonal product basis with n parties each holding a \(\frac{1}{2}(n+1)\)-dimensional system, where \(n\ge 5\) and n is odd. The proof of the local indistinguishability of the basis exhibits that it is a sufficient condition for the local indistinguishability of an orthogonal multipartite product basis that all the positive operator-valued measure elements of each party can only be proportional to the identity operator to make further discrimination feasible. Then, we construct a set of n-partite product states, which contains only 2n members and cannot be perfectly distinguished by local operations and classic communication. All the results lead to a better understanding of the phenomenon of quantum nonlocality without entanglement in multipartite and high-dimensional quantum systems.     

Tilings of nonorientable surfaces by Steiner triple systems

A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ? STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces.     

Algorithms for the Orthographic-<Emphasis Type="Italic">n</Emphasis>-Point Problem

We examine the orthographic-n-point problem (OnP), which extends the perspective-n-point problem to telecentric cameras. Given a set of 3D points and their corresponding 2D points under orthographic projection, the OnP problem is the determination of the pose of the 3D point cloud with respect to the telecentric camera. We show that the OnP problem is equivalent to the unbalanced orthogonal Procrustes problem for non-coplanar 3D points and to the sub-Stiefel Procrustes problem for coplanar 3D points. To solve the OnP problem, we apply existing algorithms for the respective Procrustes problems and also propose novel algorithms. Furthermore, we evaluate the algorithms to determine their robustness and speed and conclude which algorithms are preferable in real applications. Finally, we evaluate which algorithm is most suitable as a minimal solver in a RANSAC scheme.     

Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. I

We consider a game between a group of n pursuers and one evader moving with the same maximum velocity along the 1-skeleton graph of a regular polyhedron. The goal of the paper is finding, for each regular polyhedron M, a number N(M) with the following properties: if n ≥ N(M), the group of pursuers wins, while if n < N(M), the evader wins. Part I of the paper is devoted to the case of polyhedra in ?³; Part II will be devoted to the case of ? ^d , d ≥ 5; and Part III, to the case of ?⁴.     

Eigenvalue condition numbers and pseudospectra of Fiedler matrices

The aim of the present paper is to analyze the behavior of Fiedler companion matrices in the polynomial root-finding problem from the point of view of conditioning of eigenvalues. More precisely, we compare: (a) the condition number of a given root \({\lambda }\) of a monic polynomial p(z) with the condition number of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z), (b) the condition number of \({\lambda }\) as an eigenvalue of an arbitrary Fiedler matrix with the condition number of \({\lambda }\) as an eigenvalue of the classical Frobenius companion matrices, and (c) the pseudozero sets of p(z) and the pseudospectra of any Fiedler matrix of p(z). We prove that, if the coefficients of the polynomial p(z) are not too large and not all close to zero, then the conditioning of any root \({\lambda }\) of p(z) is similar to the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z). On the contrary, when p(z) has some large coefficients, or they are all close to zero, the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix can be arbitrarily much larger than its conditioning as a root of p(z) and, moreover, when p(z) has some large coefficients there can be two different Fiedler matrices such that the ratio between the condition numbers of \({\lambda }\) as an eigenvalue of these two matrices can be arbitrarily large. Finally, we relate asymptotically the pseudozero sets of p(z) with the pseudospectra of any given Fiedler matrix of p(z), and the pseudospectra of any two Fiedler matrices of p(z).