On enumeration of polynomial equivalence classes and their application to MPKC

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated to IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto–Imai scheme.     

Chromatic equivalence classes of complete tripartite graphs

Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph K_m,n,r are developed. Using these, we obtain the chromatic equivalence classes for K_m,n,n (where 1≤m≤n) and K_m1,m2,m3 (where |m_i−m_j|≤3). In particular, it is shown that (i) K_m,n,n (where 2≤m≤n) and (ii) K_m1,m2,m3 (where |m_i−m_j|≤3, 2≤m_i,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs K_n1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186].     

Parameter spaces for curves on surfaces and enumeration of rational curves

Let S be a smooth, minimal rational surface. The geometry of the Severi variety parametrising irreducible, rational curves in a given linear system on S is studied. The results obtained are applied to enumerative geometry, in combination with ideas from Quantum Cohomology. Formulas enumerating rational curves are found, some of which generalised Kontsevich's formula for plane curves.     

New classes of test polynomials of polynomial algebras

A polynomialp in a polynomial algebra over a field is called a test polynomial if any endomorphism of the polynomial algebra that fixesp is an automorphism. some classes of new test polynomials recognizing nonlinear automorphisms of polynomial algebras are given. In the odd prime characteristic case, test polynomials recognizing non-semisimple automorphisms are also constructed. Project supported by the National Natural Science Foundation of China (Grant No. 19631100) and University of Hong Kong RGC Fundable Grant 344/024/0004.     

On the enumeration of polynomials with prescribed factorization pattern

We use generating functions over group rings to count polynomials over finite fields with the first few coefficients and a factorization pattern prescribed. In particular, we obtain different exact formulas for the number of monic n-smooth polynomials of degree m over a finite field, as well as the number of monic n-smooth polynomials of degree m with the prescribed trace coefficient.     

On the classification of geometric codes by polynomial functions

It is shown how to represent algebraically all functions that have a zero sum on all -dimensional subspaces ofPG(n,q) or ofAG(n,q). In this way one can calculate the dimensions of related codes, or one can represent interesting sets of points by functions.     

On polynomial approximations to AC

Classical approximation results show that any circuit of size and depth has an ‐error probabilistic polynomial over the reals of degree . We improve this upper bound to , which is much better for small values of . We then use this result to show that ‐wise independence fools circuits of size and depth up to error at most , improving on Tal's strengthening of Braverman's result that ‐wise independence suffices. To our knowledge, this is the first PRG construction for that achieves optimal dependence on the error . We also prove lower bounds on the best polynomial approximations to . We show that any polynomial approximating the function on bits to a small constant error must have degree at least . This result improves exponentially on a result of Meka, Nguyen, and Vu (Theory Comput. 2016).     

On the computation of solutions of systems of interval polynomial equations

Systems of algebraic equations with interval coefficients are very common in several areas of engineering sciences. The computation of the solution of such systems is a central problem when the characterization of the variables related by such systems is desired.In this paper we characterize the solution of systems of algebraic equations with real interval coefficients. The characterization is obtained considering the approach introduced in J. Comput. Appl. Math. 136 (2001) 271.     

On symmetry of discrete polynomial hypergroups

Let be a discrete polynomial hypergoup on with Plancherel measure If the hypergroup is symmetric, the set of characters can be identified with a compact subset of the real line which contains the support of We show that the lower and upper bounds of and coincide. In particular, the trivial character belongs to the support of the Plancherel measure.

     

On polynomial interpolation of two variables

Polynomial interpolation of two variables based on points that are located on multiple circles is studied. First, the poisedness of a Birkhoff interpolation on points that are located on several concentric circles is established. Second, using a factorization method, the poisedness of a Hermite interpolation based on points located on various circles, not necessarily concentric, is established. Even in the case of Lagrange interpolation, this gives many new sets of poised interpolation points.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

On some geometry and equivalence classes of normal form games

Equivalence classes of normal form games are defined using the discontinuities of correspondences of standard equilibrium concepts like correlated, Nash, and robust equilibrium, or risk dominance and rationalizability. Resulting equivalence classes are fully characterized and compared across different equilibrium concepts for 2 ×  2 games; larger games are also studied. It is argued that the procedure leads to broad and game-theoretically meaningful distinctions of games as well as to alternative ways of representing, comparing and testing equilibrium concepts.     

On some properties of coordinates in polynomial rings

In this paper, we study some properties of coordinates in the polynomial ring by introducing some concepts which are weaker than coordinates. In particular, in the polynomial ring in two variables over an algebraically closed field of characteristic zero, we show some relations between polynomials and their fibers on 𝔸².     

Index sets of classes of automatic structures

We obtain exact estimates in the arithmetical and analytical hierarchies of index sets of various classes of automatic models. We also obtain estimates for the existence problems for computable isomorphism and embedding of automatic structures.     

Complexity of some natural problems in automatic structures

We prove that the automatic isomorphism problem for automatic structures, the automatic automorphism problem for an automatic structure, and the automatic embedding problem for automatic structures are $ \overset{\lower0.5em\hbox{$ \overset{\lower0.5em\hbox{ Matematicheski $ \overset{\lower0.5em\hbox{$ \overset{\lower0.5em\hbox{ Zhurnal, Vol. 46, No. 1, pp. 71–78, January–February, 2005.     

On the polynomial closure in a valued field

Let D be an integral domain with quotient field K. For any subset S of K, the D-polynomial closure of S is the largest subset T of K such that, for every polynomial f in K[X], if f maps S into D then f maps also T into D. When D is not local, the D-polynomial closure is not a topological closure. We prove here that, when D is any rank-one valuation domain, then there exists a topology on K such that the closed subsets for this topology are exactly the D-polynomially closed subsets of K.     

On the general cubic decomposition of polynomial sequences

We present the main results about the general cubic decomposition (CD) of polynomial sequences. We deal particularly with the diagonal CD and the CD of orthogonal sequences. This allows us to generalize a result of Barrucand and Dickinson about the CD of a symmetric orthogonal sequence.     

On the equivalence of codes over rings and modules

In light of the result by Wood that codes over every finite Frobenius ring satisfy a version of the MacWilliams equivalence theorem, a proof for the converse is considered. A strategy is proposed that would reduce the question to problems dealing only with matrices over finite fields. Using this strategy, it is shown, among other things, that any left MacWilliams basic ring is Frobenius. The results and techniques in the paper also apply to related problems dealing with codes over modules.