Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

Composing Power Series Over a Finite Ring in Essentially Linear Time

Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn^1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic.     

Fast Constructive Recognition of a Black Box Group Isomorphic toSnorAnusing Goldbach’s Conjecture

The well-known Goldbach Conjecture (GC) states that any sufficiently large even number can be represented as a sum of two odd primes. Although not yet demonstrated, it has been checked for integers up to 10¹⁴. Using two stronger versions of the conjecture, we offer a simple and fast method for recognition of a gray box group G known to be isomorphic to S_n(or A_n) with knownn ≥  20, i.e. for construction1of an isomorphism from G toS_n (or A_n). Correctness and rigorous worst case complexity estimates rely heavily on the conjectures, and yield times of O([ρ + ν + μ ] n log²n) or O([ ρ + ν + μ ] n logn / loglog n) depending on which of the stronger versions of the GC is assumed to hold. Here,ρ is the complexity of generating a uniform random element of G, ν is the complexity of finding the order of a group element in G, and μ is the time necessary for group multiplication in G. Rigorous lower bound and probabilistic approach to the time complexity of the algorithm are discussed in the Appendix.     

Computing Modular Invariants of p-groups

Let V be a finite dimensional representation of a p -group, G, over a field,k , of characteristic p. We show that there exists a choice of basis and monomial order for which the ring of invariants, k [ V ]^G, has a finite SAGBI basis. We describe two algorithms for constructing a generating set for k [ V ] G. We use these methods to analyse k [2V₃ ]^U₃where U₃is the p -Sylow subgroup ofGL₃ (F_p) and 2 V₃is the sum of two copies of the canonical representation. We give a generating set for k [2 V₃]^U₃forp =  3 and prove that the invariants fail to be Cohen–Macaulay forp >  2. We also give a minimal generating set for k [mV₂ ]^Z / pwere V₂is the two-dimensional indecomposable representation of the cyclic group Z / p.     

Bounds for the Roots of Lacunary Polynomials

A polynomial P(X)  = X^d + a_d − 1X^d − 1 + ⋯ is called lacunary when a_d − 1 =  0. We give bounds for the roots of such polynomials with complex coefficients. These bounds are much smaller than for general polynomials.     

On the Practical Solution of Genus Zero Diophantine Equations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at least three infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Some elaborated examples are given.     

Performance analysis of networks of queues under active queue management scheme

Analysis of networks of queues under repetitive service blocking mechanism has been presented in this paper. Nodes are connected according to an arbitrary configuration and each node in the networks employs an active queue management (AQM) based queueing policy to guarantee certain quality of service for multiple class external traffic. This buffer management scheme has been implemented using queue thresholds. The use of queue thresholds is a well known technique for network traffic congestion control. The analysis is based on a queue-by-queue decomposition technique where each queue is modelled as a GE/GE/1/N queue with single server, R (R ⩾ 2) distinct traffic classes and {N = N₁, N₂, … , N_R} buffer threshold values per class under first-come-first-serve (FCFS) service rule. The external traffic is modelled using the generalised exponential (GE) distribution which can capture the bursty property of network traffic. The analytical solution is obtained using the maximum entropy (ME) principle. The forms of the state and blocking probabilities are analytically established at equilibrium via appropriate mean value constraints. The initial numerical results demonstrate the credibility of the proposed analytical solution.     

Curves of Genus 2 with (N,N) Decomposable Jacobians

Let C be a curve of genus 2 and ψ₁: C  −  → E ₁  a map of degree n, from C to an elliptic curveE₁ , both curves defined over C. This map induces a degree n map φ₁:P¹  −  → P ¹  which we call a Frey–Kani covering. We determine all possible ramifications for φ₁. If ψ₁:C  −  → E ₁  is maximal then there exists a maximal map ψ₂: C  −  → E ₂  , of degree n, to some elliptic curveE₂ such that there is an isogeny of degree n²from the JacobianJ_C to E₁ × E₂. We say thatJ_C is (n, n)-decomposable. If the degree n is odd the pair (ψ₂, E₂) is canonically determined. For n =  3, 5, and 7, we give arithmetic examples of curves whose Jacobians are (n, n)-decomposable.     

Solving Genus Zero Diophantine Equations with at Most Two Infinite Valuations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at most two infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Several elaborated examples are given. Furthermore, a necessary and sufficient condition for a curve of genus 0 to have infinitely many integer points is obtained.     

On decidability of monadic logic of order over the naturals extended by monadic predicates

A fundamental result of Büchi states that the set of monadic second-order formulas true in the structure (Nat,  <) is decidable. A natural question is: what monadic predicates (sets) can be added to (Nat,  <) while preserving decidability? Elgot and Rabin found many interesting predicates P for which the monadic theory of 〈Nat, <,  P〉 is decidable. The Elgot and Rabin automata theoretical method has been generalized and sharpened over the years and their results were extended to a variety of unary predicates. We give a sufficient and necessary model-theoretical condition for the decidability of the monadic theory of (Nat, <, P₁, … , P_n).We reformulate this condition in an algebraic framework and show that a sufficient condition proposed previously by O. Carton and W.Thomas is actually necessary. A crucial argument in the proof is that monadic second-order logic has the selection and the uniformization properties over the extensions of (Nat, <) by monadic predicates. We provide a self-contained proof of this result.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Finite elements for elliptic problems with stochastic coefficients

We describe a deterministic finite element (FE) solution algorithm for a stochastic elliptic boundary value problem (sbvp), whose coefficients are assumed to be random fields with finite second moments and known, piecewise smooth two-point spatial correlation function. Separation of random and deterministic variables (parametrization of the uncertainty) is achieved via a Karhunen–Loève (KL) expansion. An O(N log N) algorithm for the computation of the KL eigenvalues is presented, based on a kernel independent fast multipole method (FMM). Truncation of the KL expansion gives an (M, 1) Wiener polynomial chaos (PC) expansion of the stochastic coefficient and is shown to lead to a high dimensional, deterministic boundary value problem (dbvp). Analyticity of its solution in the stochastic variables with sharp bounds for the domain of analyticity are used to prescribe variable stochastic polynomial degree r = (r₁, …, r_M) in an (M, r) Wiener PC expansion for the approximate solution. Pointwise error bounds for the FEM approximations of KL eigenpairs, the truncation of the KL expansion and the FE solution to the dbvp are given. Numerical examples show that M depends on the spatial correlation length of the random diffusion coefficient. The variable polynomial degree r in PC-stochastic Galerkin FEM allows to handle KL expansions with M up to 30 and r₁ up to 10 in moderate time.     

Bounds for Absolute Positiveness of Multivariate Polynomials

A multivariate polynomialP(x₁, …,x_n) with real coefficients is said to beabsolutely positivefrom a real numberBiff it and all of its non-zero partial derivatives of every order are positive forx₁,…,x_n ≧ B. We call suchBaboundfor the absolute positiveness ofP. This paper provides a simple formula for computing such bounds. We also prove that the resulting bounds are guaranteed to be close to the optimal ones.     

On identifying codes that are robust against edge changes

Assume that G = (V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote I_r(G; v) = {u ∈ C: d(u,v) ≤ r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets I_r(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.     

An Algorithm for the Quillen–Suslin Theorem for Quotients of Polynomial Rings by Monomial Ideals

This paper presents an algorithm for the Quillen–Suslin Theorem for quotients of polynomial rings by monomial ideals, that is, quotients of the form A = k [ x₀, . . . ,x_n ] / I, with I a monomial ideal and k a field. Vorst proved that finitely generated projective modules over such algebras are free. Given a finitely generated module P, described by generators and relations, the algorithm tests whether P is projective, in which case it computes a free basis forP .     

On reliability of the folded hypercubes

In this paper, we explore the 2-extra connectivity and 2-extra-edge-connectivity of the folded hypercube FQ_n. We show that κ₂(FQ_n) = 3n − 2 for n ⩾ 8; and λ₂(FQ_n) = 3n − 1 for n ⩾ 5. That is, for n ⩾ 8 (resp. n ⩾ 5), at least 3n − 2 vertices (resp. 3n − 1 edges) of FQ_n are removed to get a disconnected graph that contains no isolated vertices (resp. edges). When the folded hypercube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

Evaluation of the absolute affinity of neuraminidase inhibitor using steered molecular dynamics simulations

The absolute free energy difference of binding (ΔG) between neuraminidase and its inhibitor was evaluated using fast pulling of ligand (FPL) method over steered molecular dynamics (SMD) simulations. The metric was computed through linear interaction approximation. Binding nature was described by free energy differences of electrostatic and van der Waals (vdW) interactions. The finding indicates that vdW metric is dominant over electrostatics in binding process. The computed values are in good agreement with experimental data with a correlation coefficient of R = 0.82 and error of σΔG_exp = 2.2 kcal/mol. The results were observed using Amber99SB-ILDN force field in comparison with CHARMM27 and GROMOS96 43a1 force fields. Obtained results may stimulate the search for an Influenza therapy.     

Taylor approximation for hybrid systems

We propose a new approximation technique for Hybrid Automata. Given any Hybrid Automaton H, we call Approx(H, k) the Polynomial Hybrid Automaton obtained by approximating each formula ϕ in H with the formulae ϕ_k obtained by replacing the functions in ϕ with their Taylor polynomial of degree k. We prove that Approx(H, k) is an over-approximation of H. We study the conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any vector satisfying ϕ_k and at least one vector satisfying ϕ is less than ϵ. We study also conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any configuration reached by Approx(H, k) in n steps and at least one configuration reached by H in n steps is less than ϵ.