The weight distributions of a class of cyclic codes II

Recently, the weight distributions of the duals of the cyclic codes with two zeros have been obtained for several cases in Ding et al. (IEEE Trans Inform Theory 57(12), 8000–8006, 2011); Ma et al. (IEEE Trans Inform Theory 57(1):397–402, 2011); Wang et al. (Trans Inf Theory 58(12):7253–7259, 2012); and Xiong (Finite Fields Appl 18(5):933–945, 2012). In this paper we use the method developed in Xiong (Finite Fields Appl 18(5):933–945, 2012) to solve one more special case. We make extensive use of standard tools in number theory such as characters of finite fields, the Gauss sums and the Jacobi sums. The problem of finding the weight distribution is transformed into a problem of evaluating certain character sums over finite fields, which turns out to be associated with counting the number of points on some elliptic curves over finite fields. We also treat the special case that the characteristic of the finite field is 2.     

List decoding of number field codes

This paper presents a list decoding algorithm for the number field codes of Guruswami (IEEE Trans Inf Theory 49:594–603, 2003). The algorithm is an implementation of the unified framework for list decoding of algebraic codes of Guruswami, Sahai and Sudan (Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000), specialised for number field codes. The computational complexity of the algorithm is evaluated in terms of the size of the inputs and field invariants.     

Optimal Identifying Codes in Cycles and Paths

The concept of identifying codes in a graph was introduced by Karpovsky et?al. (in IEEE Trans Inf Theory 44(2):599–611, 1998). These codes have been studied in several types of graphs such as hypercubes, trees, the square grid, the triangular grid, cycles and paths. In this paper, we determine the optimal cardinalities of identifying codes in cycles and paths in the remaining open cases.     

Cryptanalytic results on ‘Dual CRT’ and ‘Common Prime’ RSA

In this paper we study weaknesses of two variants of RSA: Dual RSA and Common Prime RSA. Several schemes under the framework of Dual RSA have been proposed by Sun et al. (IEEE Trans Inf Theory 53(8):2922–2933, 2007). We here concentrate on the Dual CRT-RSA scheme and present certain range of parameters where it is insecure. As a corollary of our work, we prove that the Dual Generalized Rebalanced-RSA (Scheme III of Sun et al.) can be efficiently broken for a significant region where the scheme has been claimed to be secure. Next we consider the Common Prime RSA as proposed by Wiener (IEEE Trans. Inf. Theory 36:553–558, 1990). We present new range of parameters in Common Prime RSA where it is not secure. We use lattice based techniques for the attacks.     

Index sets and Scott sentences

For a computable structure \({\mathcal{A}}\) , there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence \({\varphi}\) , then the complexity of the index set \({I(\mathcal{A})}\) is bounded by that of \({\varphi}\) . There are results (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012; Knight and Saraph in Scott sentences for certain groups, pre-print) giving “optimal” Scott sentences for structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012). In this note, it is shown that the thesis does not always hold. For a certain subgroup of \({\mathbb{Q}}\) , there is no computable d- \({\Sigma_2}\) Scott sentence, even though (as shown in Ash and Knight in Scott sentences for certain groups, pre-print) the index set is d- \({\Sigma^0_2}\) .     

Constructive spherical codes near the Shannon bound

Shannon gave a lower bound in 1959 on the binary rate of spherical codes of given minimum Euclidean distance ρ. Using nonconstructive codes over a finite alphabet, we give a lower bound that is weaker but very close for small values of ρ. The construction is based on the Yaglom map combined with some finite sphere packings obtained from nonconstructive codes for the Euclidean metric. Concatenating geometric codes meeting the TVZ bound with a Lee metric BCH code over GF(p), we obtain spherical codes that are polynomial time constructible. Their parameters outperform those obtained by Lachaud and Stern (IEEE Trans Inf Theory 40(4):1140–1146, 1994). At very high rate they are above 98% of the Shannon bound.     

Exponents of polar codes using algebraic geometric code kernels

Reed–Solomon and BCH codes were considered as kernels of polar codes by Mori and Tanaka (IEEE Information Theory Workshop, 2010, pp 1–5) and Korada et al. (IEEE Trans Inform Theory 56(12):6253–6264, 2010) to create polar codes with large exponents. Mori and Tanaka showed that Reed–Solomon codes over the finite field \(\mathbb {F}_q\) with \(q\) elements give the best possible exponent among all codes of length \(l \le q\) . They also stated that a Hermitian code over \(\mathbb {F}_{2^r}\) with \(r \ge 4\) , a simple algebraic geometric code, gives a larger exponent than the Reed–Solomon matrix over the same field. In this paper, we expand on these ideas by employing more general algebraic geometric (AG) codes to produce kernels of polar codes. Lower bounds on the exponents are given for kernels from general AG codes, Hermitian codes, and Suzuki codes. We demonstrate that both Hermitian and Suzuki kernels have larger exponents than Reed–Solomon codes over the same field, for \(q \ge 3\) ; however, the larger exponents are at the expense of larger kernel matrices. Comparing kernels of the same size, though over different fields, we see that Reed–Solomon kernels have larger exponents than both Hermitian and Suzuki kernels. These results indicate a tradeoff between the exponent, kernel matrix size, and field size.     

The multicovering radius problem for some types of discrete structures

The covering radius problem is a question in coding theory concerned with finding the minimum radius r such that, given a code that is a subset of an underlying metric space, balls of radius r over its code words cover the entire metric space. Klapper (IEEE Trans. Inform. Theory 43:1372–1377, 1997) introduced a code parameter, called the multicovering radius, which is a generalization of the covering radius. In this paper, we introduce an analogue of the multicovering radius for permutation codes (Des. Codes Cryptogr. 41:79–86, cf. 2006) and for codes of perfect matchings (cf. 2012). We apply probabilistic tools to give some lower bounds on the multicovering radii of these codes. In the process of obtaining these results, we also correct an error in the proof of the lower bound of the covering radius that appeared in (Des. Codes Cryptogr. 41:79–86, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.     

Two optimal one-error-correcting codes of length 13 that are not doubly shortened perfect codes

The optimal one-error-correcting codes of length 13 that are doubly shortened perfect codes are classified utilizing the results of [Östergård, P.R.J., Pottonen, O.: The perfect binary one-error-correcting codes of length 15: Part I??Classification. IEEE Trans. Inform. Theory 55, 4657?C4660 (2009)]; there are 117821 such (13,512,3) codes. By applying a switching operation to those codes, two more (13,512,3) codes are obtained, which are then not doubly shortened perfect codes.     

Right-convergence of sparse random graphs

The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs \(\mathbb{G }_N, N\ge 1\) to some target graph \(W\) . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151–219, 2012; Borgs et al. in Adv Math 219:1801–1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000–1017, 2011; Lovász and Szegedy in J Comb Theory Ser B 96:933–957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with \(W\) . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph \(W\) satisfies a certain convexity property. We treat the case of discrete and continuous target graphs \(W\) . The latter case allows us to prove a special case of Talagrand’s recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from \(\mathbb{R }^N\) by intersecting it with linearly in \(N\) many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71–79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdös-Rényi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535–564, 2003; Franz et al. in J Phys A Math Gen 36:10967–10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221–3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312–336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdös-Rényi graphs for some special cases of \(W\) . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.     

Polynomial growth harmonic functions on finitely generated abelian groups

In the present paper, we develop geometric analysis techniques on Cayley graphs of finitely generated abelian groups to study the polynomial growth harmonic functions. We provide a geometric analysis proof of the classical Heilbronn theorem (Heilbronn in Proc Camb Philos Soc 45:194–206, 1949) and the recent Nayar theorem (Nayar in Bull Pol Acad Sci Math 57:231–242, 2009) on polynomial growth harmonic functions on lattices $\mathbb Z ^n$ that does not use a representation formula for harmonic functions. In the abelian group case, by Yau’s gradient estimate, we actually give a simplified proof of a general polynomial growth harmonic function theorem of (Alexopoulos in Ann Probab 30:723–801, 2002). We calculate the precise dimension of the space of polynomial growth harmonic functions on finitely generated abelian groups by linear algebra, rather than by Floquet theory Kuchment and Pinchover (Trans Am Math Soc 359:5777–5815, 2007). While the Cayley graph not only depends on the abelian group, but also on the choice of a generating set, we find that this dimension depends only on the group itself. Moreover, we also calculate the dimension of solutions to higher order Laplace operators.     

Asymptotic Optimality of Scalar Gersho Quantizers

In his famous paper (Gersho, IEEE Trans. Inf. Theory 25(4):373–380, 1979), Gersho stressed that the codecells of optimal quantizers asymptotically make an equal contribution to the distortion of the quantizer. Motivated by this fact, we investigate in this paper quantizers in the scalar case, where each codecell contributes with exactly the same portion to the quantization error. We show that such quantizers of Gersho type—or Gersho quantizers for short—exist for nonatomic scalar distributions. As a main result, we prove that Gersho quantizers are asymptotically optimal.     

Universal integrals based on copulas

A hierarchical family of integrals based on a fixed copula is introduced and discussed. The extremal members of this family correspond to the inner and outer extension of integrals of basic functions, the copula under consideration being the corresponding multiplication. The limits of the members of the family are just copula-based universal integrals as recently introduced in Klement et al. (IEEE Trans Fuzzy Syst 18:178–187, 2010). For the product copula, the family of integrals considered here contains the Choquet and the Shilkret integral, and it belongs to the class of decomposition integrals proposed in Even and Lehrer (Econ Theory, 2013) as well as to the class of superdecomposition integrals introduced in Mesiar et al. (Superdecomposition integral, 2013). For the upper Fréchet-Hoeffding bound, the corresponding hierarchical family contains only two elements: all but the greatest element coincide with the Sugeno integral.     

A comparative assessment of different fuzzy regression methods for volatility forecasting

The aim of this paper is to compare different fuzzy regression methods in the assessment of the information content on future realised volatility of option-based volatility forecasts. These methods offer a suitable tool to handle both imprecision of measurements and fuzziness of the relationship among variables. Therefore, they are particularly useful for volatility forecasting, since the variable of interest (realised volatility) is unobservable and a proxy for it is used. Moreover, measurement errors in both realised volatility and volatility forecasts may affect the regression results. We compare both the possibilistic regression method of Tanaka et al. (IEEE Trans Syst Man Cybern 12:903–907, 1982) and the least squares fuzzy regression method of Savic and Pedrycz (Fuzzy Sets Syst 39:51–63, 1991). In our case study, based on intra-daily data of the DAX-index options market, both methods have proved to have advantages and disadvantages. Overall, among the two methods, we prefer the Savic and Pedrycz (Fuzzy Sets Syst 39:51–63, 1991) method, since it contains as special case (the central line) the ordinary least squares regression, is robust to the analysis of the variables in logarithmic terms or in levels, and provides sharper results than the Tanaka et al. (IEEE Trans Syst Man Cybern 12:903–907, 1982) method.     

Quadratic functions with prescribed spectra

We study a class of quadratic p-ary functions ${{\mathcal{F}}_{p,n}}$ from ${\mathbb{F}_{p^n}}$ to ${\mathbb{F}_p, p \geq 2}$ , which are well-known to have plateaued Walsh spectrum; i.e., for each ${b \in \mathbb{F}_{p^n}}$ the Walsh transform ${\hat{f}(b)}$ satisfies ${|\hat{f}(b)|^2 \in \{ 0, p^{(n+s)}\}}$ for some integer 0 ≤ s ≤ n ? 1. For various types of integers n, we determine possible values of s, construct ${{\mathcal{F}}_{p,n}}$ with prescribed spectrum, and present enumeration results. Our work generalizes some of the earlier results, in characteristic two, of Khoo et. al. (Des Codes Cryptogr, 38, 279–295, 2006) and Charpin et al. (IEEE Trans Inf Theory 51, 4286–4298, 2005) on semi-bent functions, and of Fitzgerald (Finite Fields Appl 15, 69–81, 2009) on quadratic forms.     

Small tight sets of hyperbolic quadrics

An x-tight set of a hyperbolic quadric Q ⁺(2n + 1, q) can be described as a set M of points with the property that the number of points of M in the tangent hyperplanes of points of M is as big as possible. We show that such a set is necessarily the union of x mutually disjoint generators provided that x ≤ q and n ≤ 3, or that x < q, n ≥ 4 and q ≥ 71. This unifies and generalizes many results on x-tight sets that are presently known, see (J Comb Theory Ser A 114(7):1293–1314 [1], J Comb Des 16(4):342–349 [5], Des Codes Cryptogr 50:187–201 [4], Adv Geom 4(3):279–286 [8], Bull Lond Math Soc 42(6):991–996 [11]).     

Continuity of the solution mapping to parametric generalized vector equilibrium problems

In this paper, two kinds of parametric generalized vector equilibrium problems in normed spaces are studied. The sufficient conditions for the continuity of the solution mappings to the two kinds of parametric generalized vector equilibrium problems are established under suitable conditions. The results presented in this paper extend and improve some main results in Chen and Gong (Pac J Optim 3:511–520, 2010), Chen and Li (Pac J Optim 6:141–152, 2010), Chen et al. (J Glob Optim 45:309–318, 2009), Cheng and Zhu (J Glob Optim 32:543–550, 2005), Gong (J Optim Theory Appl 139:35–46, 2008), Li and Fang (J Optim Theory Appl 147:507–515, 2010), Li et al. (Bull Aust Math Soc 81:85–95, 2010) and Peng et al. (J Optim Theory Appl 152(1):256–264, 2011).     

Metric intersection problems in Cayley graphs and the Stirling recursion

In Sym(n) with n ≥ 5 let H be a conjugacy class of elements of order 2 and let Γ be the Cayley graph whose vertex set is the group G generated by H (so G = Sym(n) or Alt(n)) and whose edge set is determined by H. We are interested in the metric structure of this graph. In particular, for ${g \in G}$ let B _r (g) be the metric ball in Γ of radius r and centre g. We show that the intersection numbers ${\Phi(\Gamma; r, g) := |\,B_{r}(e)\,\cap\,B_{r}(g)\,|}$ are generalized Stirling functions in n and r. The results are motivated by the study of error graphs in Levenshtein (Dokl Akad Nauk 354:593–596, 1997; IEEE Trans Inform Theory 47(1):2–22, 2001; (J Comb Theory Ser A 93(2):310–332, 2001) and related reconstruction problems.     

Construction of cyclotomic codebooks nearly meeting the Welch bound

Ding and Feng (IEEE Trans Inform Theory 52(9):4229–4235, 2006, IEEE Trans Inform Theory 53(11):4245–4250, 2007) constructed series of (N, K) codebooks which meet or nearly meet the Welch bound \({\sqrt{\frac{N-K}{(N-1)K}}}\) by using difference set (DS) or almost difference set (ADS) in certain finite abelian group respectively. In this paper, we generalize the cyclotomic constructions considered in (IEEE Trans Inform Theory 52(9):4229–4235, 2006, IEEE Trans Inform Theory 53(11):4245–4250, 2007) and (IEEE Trans Inform Theory 52(5), 2052–2061, 2006) to present more series of codebooks which nearly meet the Welch bound under looser conditions than ones required by DS and ADS.     

On the lower semicontinuity of the solution mappings to a parametric generalized strong vector equilibrium problem

In this paper, under new assumptions, which do not contain any information about the solution set, the lower semicontinuity of solution mappings to a parametric generalized strong vector equilibrium problem are established by using a scalarization method. These results extend and generalize the corresponding ones in Gong and Yao (J Optim Theory Appl 138:197–205, 2008), Chen and Li (Pac J Optim 6:141–151, 2010) and Li et al. (2012, submitted). Some examples are given to illustrate our results.