No decreasing sequence of cardinals

In set theory without the Axiom of Choice (AC), we investigate the set-theoretic strength of the principle NDS which states that there is no function f on the set ω of natural numbers such that for everyn ∈ ω, f (n + 1) ? f (n), where for sets x and y, x ? y means that there is a one-to-one map g : x → y, but no one-to-one map h : y → x. It is a long standing open problem whether NDS implies AC. In this paper, among other results, we show that NDS is a strong axiom by establishing that AC^LO (AC restricted to linearly ordered sets of non-empty sets, and also equivalent to AC in ZF, the Zermelo–Fraenkel set theory minus AC) ? NDS in ZFA set theory (ZF with the Axiom of Extensionality weakened in order to allow the existence of atoms). The latter result provides a strongly negative answer to the question of whether “every Dedekind-finite set is finite” implies NDS addressed in G. H. Moore “Zermelo’s Axiom of Choice. Its Origins, Development, and Influence” and in P. Howard–J. E. Rubin “Consequences of the Axiom of Choice”. We also prove that AC^WO (AC restricted to well-ordered sets of non-empty sets) ? NDS in ZF (hence, “every Dedekind-finite set is finite” ? NDS in ZF, either) and that “for all infinite cardinals m, m + m = m” ? NDS in ZFA.     

Kleisli Monoids Describing Approach Spaces

We study the functional ideal monad \(\mathbb {I} = (\mathsf {I}, m, e)\) on S e t and show that this monad is power-enriched. This leads us to the category \(\mathbb {I}\)- M o n of all \(\mathbb {I}\)-monoids with structure preserving maps. We show that this category is isomorphic to A p p, the category of approach spaces with contractions as morphisms. Through the concrete isomorphism, an \(\mathbb {I}\)-monoid (X,ν) corresponds to an approach space \((X, \mathfrak {A}),\) described in terms of its bounded local approach system. When I is extended to R e l using the Kleisli extension \(\check {\mathsf {I}},\) from the fact that \(\mathbb {I}\)- M o n and \((\mathbb {I},2)\)- C a t are isomorphic, we obtain the result that A p p can be isomorphically described in terms of convergence of functional ideals, based on the two axioms of relational algebras, reflexivity and transitivity. We compare these axioms to the ones put forward in Lowen (2015). Considering the submonad \(\mathbb {B}\) of all prime functional ideals, we show that it is both sup-dense and interpolating in \(\mathbb {I}\), from which we get that \((\mathbb {I},2)\)- C a t and \((\mathbb {B},2)\)- C a t are isomorphic. We present some simple axioms describing A p p in terms of prime functional ideal convergence.     

Rigidity of unary algebras and its application to the $${\mathcal {HS} = \mathcal {SH}}$$ problem

H. P. Gumm and T. Schröder stated a conjecture that the preservation of preimages by a functor T for which |T1| = 1 is equivalent to the satisfaction of the class equality \({{\mathcal {HS}}({\sf K}) = {\mathcal {SH}}({\sf K})}\) for any class K of T-coalgebras. Although T. Brengos and V. Trnková gave a positive answer to this problem for a wide class of Set-endofunctors, they were unable to find the full solution. Using a construction of a rigid unary algebra we prove \({{\mathcal {HS}} \neq {\mathcal {SH}}}\) for a class of Set-endofunctors not preserving non-empty preimages; these functors have not been considered previously.     

Equiconsistencies at subcompact cardinals

We present equiconsistency results at the level of subcompact cardinals. Assuming SBH_δ, a special case of the Strategic Branches Hypothesis, we prove that if δ is a Woodin cardinal and both □(δ) and □_δ fail, then δ is subcompact in a class inner model. If in addition □(δ⁺) fails, we prove that δ is \({\Pi_1^2}\) subcompact in a class inner model. These results are optimal, and lead to equiconsistencies. As a corollary we also see that assuming the existence of a Woodin cardinal δ so that SBH_δ holds, the Proper Forcing Axiom implies the existence of a class inner model with a \({\Pi_1^2}\) subcompact cardinal. Our methods generalize to higher levels of the large cardinal hierarchy, that involve long extenders, and large cardinal axioms up to δ is δ⁺⁽ⁿ⁾ supercompact for all n < ω. We state some results at this level, and indicate how they are proved.     

Relative Projectivity and Transferability for Partial Lattices

A partial lattice P is ideal-projective, with respect to a class \(\mathcal {C}\) of lattices, if for every \(K\in \mathcal {C}\) and every homomorphism φ of partial lattices from P to the ideal lattice of K, there are arbitrarily large choice functions f:P→K for φ that are also homomorphisms of partial lattices. This extends the traditional concept of (sharp) transferability of a lattice with respect to \(\mathcal {C}\). We prove the following: (1) A finite lattice P, belonging to a variety \(\mathcal {V}\), is sharply transferable with respect to \(\mathcal {V}\) iff it is projective with respect to \(\mathcal {V}\) and weakly distributive lattice homomorphisms, iff it is ideal-projective with respect to \(\mathcal {V}\), (2) Every finite distributive lattice is sharply transferable with respect to the class \(\mathcal {R}_{\text {mod}}\) of all relatively complemented modular lattices, (3) The gluing D ₄ of two squares, the top of one being identified with the bottom of the other one, is sharply transferable with respect to a variety \(\mathcal {V}\) iff \(\mathcal {V}\) is contained in the variety \(\mathcal {M}_{\omega }\) generated by all lattices of length 2, (4) D ₄ is projective, but not ideal-projective, with respect to \(\mathcal {R}_{\text {mod}}\) , (5) D ₄ is transferable, but not sharply transferable, with respect to the variety \(\mathcal {M}\) of all modular lattices. This solves a 1978 problem of G. Grätzer, (6) We construct a modular lattice whose canonical embedding into its ideal lattice is not pure. This solves a 1974 problem of E. Nelson.     

Relative congruence formulas and decompositions in quasivarieties

Quasivarietal analogues of uniform congruence schemes are discussed, and their relationship with the equational definability of principal relative congruences (EDPRC) is established, along with their significance for relative congruences on subalgebras of products. Generalizing the situation in varieties, we prove that a quasivariety is relatively ideal iff it has EDPRC; it is relatively filtral iff it is relatively semisimple with EDPRC. As an application, it is shown that a finitary sentential logic, algebraized by a quasivariety K, has a classical inconsistency lemma if and only if K is relatively filtral and the subalgebras of its nontrivial members are nontrivial. A concrete instance of this result is exhibited, in which K is not a variety. Finally, for quasivarieties \({\sf{M} \subseteq \sf{K}}\), we supply some conditions under which M is the restriction to K of a variety, assuming that K has EDPRC.     

A Schur-Weyl Duality Approach toWalking on Cubes

Walks on the representation graph \({\mathcal{R}_{\mathsf{V}}}\)(G) determined by a group G and a G-module V are related to the centralizer algebras of the action of G on the tensor powers \({\mathsf{V}^{\otimes k}}\) via Schur-Weyl duality. This paper explores that connection when the group is \({\mathbb{Z}^{n}_{2}}\) and the module V is chosen so the representation graph is the n-cube. We describe a basis for the centralizer algebras in terms of labeled partition diagrams. We obtain an expression for the number of walks by counting certain partitions and determine the exponential generating functions for the number of walks.     

Canonical formulas for <Emphasis Type="Italic">k</Emphasis>-potent commutative,integral, residuated lattices

Canonical formulas are a powerful tool for studying intuitionistic and modal logics. Indeed, they provide a uniform and semantic way of axiomatising all extensions of intuitionistic logic and all modal logics above K4. Although the method originally hinged on the relational semantics of those logics, recently it has been completely recast in algebraic terms. In this new perspective, canonical formulas are built from a finite subdirectly irreducible algebra by describing completely the behaviour of some operations and only partially the behaviour of some others. In this paper, we export the machinery of canonical formulas to substructural logics by introducing canonical formulas for k-potent, commutative, integral, residuated lattices (k-CIRL). We show that any subvariety of k-CIRL is axiomatised by canonical formulas. The paper ends with some applications and examples.     

Super-strong RKA secure MAC,PKE and SE from tag-based hash proof system

\(\mathcal {F}\)-related-key attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say k, but also related keys f(k), with f adaptively chosen from \(\mathcal {F}\) by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called super-strong RKA securities, which stipulate minimal restrictions on the adversary’s forgery or oracle access, thus turn out to be the strongest ones among existing RKA security requirements. We present paradigms for constructing super-strong RKA secure MAC, PKE and SE from a common ingredient, namely Tag-based hash proof system (THPS). We also present constructions for THPS based on the k-linear and the DCR assumptions. When instantiating our paradigms with concrete THPS constructions, we obtain super-strong RKA secure MAC, PKE and SE schemes for the class of restricted affine functions \(\mathcal {F}_{\text {raff}}\), of which the class of linear functions \(\mathcal {F}_{\text {lin}}\) is a subset. To the best of our knowledge, our MACs, PKEs and SEs are the first ones possessing super-strong RKA securities for a non-claw-free function class \(\mathcal {F}_{\text {raff}}\) in the standard model and under standard assumptions. Our constructions are free of pairing and are as efficient as those proposed in previous works. In particular, the keys, tags of MAC and ciphertexts of PKE and SE all consist of only a constant number of group elements.     

Equivariant Degenerations of Spherical Modules: Part II

We determine, under a certain assumption, the Alexeev–Brion moduli scheme M of affine spherical G-varieties with a prescribed weight monoid . In Papadakis and Van Steirteghem (Ann. Inst. Fourier (Grenoble). 62(5) 1765–1809 19) we showed that if G is a connected complex reductive group of type A and is the weight monoid of a spherical G-module, then M is an affine space. Here we prove that this remains true without any restriction on the type of G.     

Weak square and stationary reflection

It is well-known that the square principle \({\square_\lambda}\) entails the existence of a non-reflecting stationary subset of λ⁺, whereas the weak square principle \({\square^{*} _\lambda}\) does not. Here we show that if μ^cf(λ) < λ for all μ < λ, then \({\square^{*} _\lambda}\) entails the existence of a non-reflecting stationary subset of \({E^{\lambda^+}_{{\rm cf}(\lambda)}}\)in the forcing extension for adding a single Cohen subset of λ⁺.It follows that indestructible forms of simultaneous stationary reflection entail the failure of weak square. We demonstrate this by settling a question concerning the subcomplete forcing axiom (SCFA), proving that SCFA entails the failure of \({\square^{*} _\lambda}\) for every singular cardinal λ of countable cofinality.     

The Cesàro Operator in Growth Banach Spaces of Analytic Functions

The Cesàro operator C, when acting in the classical growth Banach spaces \({A^{-\gamma}}\) and \({A_0^{-\gamma}}\), for \({\gamma} > 0\), of analytic functions on \({\mathbb{D}}\), is investigated. Based on a detailed knowledge of their spectra (due to A. Aleman and A.-M. Persson) we are able to determine the norms of these operators precisely. It is then possible to characterize the mean ergodic and related properties of C acting in these spaces. In addition, we determine the largest Banach space of analytic functions on \({\mathbb{D}}\) which C maps into \({A^{-\gamma}}\) (resp. into \({A_0^{-\gamma}}\)); this optimal domain space always contains \({A^{-\gamma}}\) (resp. \({A_0^{-\gamma}}\)) as a proper subspace.     

Strong authenticated key exchange with auxiliary inputs

In the Russian cards problem, Alice, Bob and Cath draw a, b and c cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Alice and Bob’s exchanges do not allow Cath to know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card. We propose an intermediate notion, which we call \(\varepsilon \)-strong security, where the probabilities perceived by Cath may only change by a factor of \(\varepsilon \). We then show that strategies based on affine or projective geometries yield \(\varepsilon \)-strong safety for arbitrarily small \(\varepsilon \) and appropriately chosen values of a, b, c.     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

The Isometry Group of an <Emphasis FontCategory="SansSerif">RCD</Emphasis><Superscript>∗</Superscript> Space is Lie

We give necessary and sufficient conditions that show that both the group of isometries and the group of measure-preserving isometries are Lie groups for a large class of metric measure spaces. In addition we study, among other examples, whether spaces having a generalized lower Ricci curvature bound fulfill these requirements. The conditions are satisfied by R C D ^?-spaces and, under extra assumptions, by C D-spaces, C D ^? P-spaces. However, we show that the M C C P-condition by itself is not enough to guarantee a smooth behavior of these automorphism groups.     

On dihedrants admitting arc-regular group actions

We consider Cayley graphs Γ over dihedral groups, dihedrants for short, which admit an automorphism group G acting regularly on the arc set of Γ. We prove that, if D _2n ≤G≤Aut(Γ) is a regular dihedral subgroup of G of order 2n such that any of its index 2 cyclic subgroups is core-free in G, then Γ belongs to the family of graphs of the form \((K_{n_{1}}\otimes\cdots\otimes K_{n_{\ell}})[K_{m}^{\mathrm{c}}]\), where 2n=n ₁???n _? m, and the numbers n _i are pairwise coprime. Applications to 1-regular dihedrants and Cayley maps on dihedral groups are also given.     

Richardson’s Theorem in <Emphasis Type="Italic">H</Emphasis>-coloured Digraphs

Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are coloured with the vertices of H (D is an H-coloured digraph). The sets V(D) and A(D) will denote the sets of vertices and arcs of D respectively. A directed path W in D is an H-path if and only if the consecutive colors encountered on W form a directed walk in H. A set \(N\subseteq \hbox {V}(D)\) is an H-kernel if for every pair of different vertices in N there is no H-path between them, and for every vertex \(u\in \hbox {V}(D){\setminus }N\) there exists an H-path in D from u to N. Let D be an m-coloured digraph. The color-class digraph of D, denoted by \({\mathscr {C}}_C(D\)), is the digraph such that: the vertices of the color-class digraph are the colors represented in the arcs of D, and \((i,j) \in A({\mathscr {C}}_C(D\))) if and only if there exist two arcs namely (u, v) and (v, w) in D such that (u, v) has color i and (v, w) has color j. Let \(W=(v_0, \ldots , v_n\)) be a directed walk in \({\mathscr {C}}_C(D)\), with D an H-coloured digraph, and \(e_i = (v_{i},v_{i+1})\) for each \(i \in \{0, \ldots ,n-1\}\). Let \(I = \{i_1, \ldots , i_k\}\) a subset of \(\{0, \ldots , n-1\}\) such that for 0 \(\le s \le n-1\), \(e_s \in \hbox { A}(H^c)\) if and only if \(s \in I\) (where \(H^c\) is the complement of H), then we will say that k is the \(H^c\)-length of W. Since V(\({\mathscr {C}}_C(D)) \subseteq \hbox {V}(H)\), the main question is: What structural properties of \({\mathscr {C}}_C(D)\), with respect to H, imply that D has an H-kernel? In this paper we will prove the following: If \({\mathscr {C}}_C(D)\) does not have directed cycles of odd \(H^c\)-length, then D has an H-kernel. Finally we will prove Richardson’s theorem as a direct consequence of the previous result.     

Non-triviality conditions for integer-valued polynomial rings on algebras

Let D be a commutative domain with field of fractions K and let A be a torsion-free D-algebra such that \(A \cap K = D\). The ring of integer-valued polynomials on A with coefficients in K is \( Int _K(A) = \{f \in K[X] \mid f(A) \subseteq A\}\), which generalizes the classic ring \( Int (D) = \{f \in K[X] \mid f(D) \subseteq D\}\) of integer-valued polynomials on D. The condition on \(A \cap K\) implies that \(D[X] \subseteq Int _K(A) \subseteq Int (D)\), and we say that \( Int _K(A)\) is nontrivial if \( Int _K(A) \ne D[X]\). For any integral domain D, we prove that if A is finitely generated as a D-module, then \( Int _K(A)\) is nontrivial if and only if \( Int (D)\) is nontrivial. When A is not necessarily finitely generated but D is Dedekind, we provide necessary and sufficient conditions for \( Int _K(A)\) to be nontrivial. These conditions also allow us to prove that, for D Dedekind, the domain \( Int _K(A)\) has Krull dimension 2.     

Spherical bodies of constant width

The intersection L of two different non-opposite hemispheres G and H of the d-dimensional unit sphere \(S^d\) is called a lune. By the thickness of L we mean the distance of the centers of the \((d-1)\)-dimensional hemispheres bounding L. For a hemisphere G supporting a convex body \(C \subset S^d\) we define \(\mathrm{width}_G(C)\) as the thickness of the narrowest lune or lunes of the form \(G \cap H\) containing C. If \(\mathrm{width}_G(C) =w\) for every hemisphere G supporting C, we say that C is a body of constant width w. We present properties of these bodies. In particular, we prove that the diameter of any spherical body C of constant width w on \(S^d\) is w, and that if \(w < \frac{\pi }{2}\), then C is strictly convex. Moreover, we check when spherical bodies of constant width and constant diameter coincide.     

Analysis of the single-permutation encrypted Davies–Meyer construction

We consider the so-called Encrypted Davies–Meyer (EDM) construction, which turns a permutation P on \(\{0,1\}^n\) into a function from \(\{0,1\}^n\) to \(\{0,1\}^n\) defined as \(P(P(x)\oplus x)\). A similar construction using two independent permutations, namely \(P'(P(x)\oplus x)\), was previously analyzed by Cogliati and Seurin (Advances in cryptology—CRYPTO 2016 (Proceedings, Part I). LNCS, vol 9814, pp. 121–149, 2016) who showed that when P and \(P'\) are secret and random, then any black-box adversary needs at least roughly \(2^{2n/3}\) queries to distinguish the construction from a uniformly random function from \(\{0,1\}^n\) to \(\{0,1\}^n\). In this paper, we focus on the single-permutation variant of the construction. Our main result is that the PRF-security of the single-permutation EDM construction is also (at least) roughly \(2^{2n/3}\), in the sense that any black-box adversary needs at least this number of queries to distinguish the construction from a uniformly random function. This yields the first PRP-to-PRF conversion method which uses a single permutation, does not shrink the original domain nor range of the permutation, and provides security beyond the birthday bound.