Number News

I'm trying to clarify the correct combinatorial model for the following problem. There is a disagreement between me and another person regarding whether to use permutations, combinations, or combinations with repetition. Problem: "Ten companies are participating in the grant competition in three nominations. Calculate the number of grant distribution options if the same grant values ​​are set for each nomination." There are two interpretations: My interpretation: The categories are distinct, even though the grant amount is the same. Each company can receive only one grant (i.e., at most one award per company). Therefore, we are selecting 3 distinct companies and assigning them to distinct categories, meaning the order matters. Thus, the number of possible distributions is a permutation (or arrangement) of 3 companies from 10: $A_{10}^3 = 10 \cdot 9 \cdot 8 = 720$ The other interpretation: A company can receive multiple grants (up to all three). Since the grant amounts are equal, the categories are treated as indistinguishable. Therefore, the model used is combinations with repetition: $C_{10 + 3 - 1}^3 = \binom{12}{3} = 220$ Question: Which interpretation is more appropriate under standard assumptions, when the problem does not explicitly state whether: A company can receive more than one grant; The categories are distinguishable despite identical grant amounts.

In bounded arithmetic (or bounded reverse mathematics) we study formal systems so weak that the structures of their proofs correspond to some known complexity classes such as PTIME, LOGSPACE or AC0. Here I will refer to the astonishing work of Steven Cook and Phuong Nguyen, "Logical Foundations of Proof Complexity" - specifically, to the draft available here: cook-nguyen.pdf, as the original is non open-access. For motivation: Conceptually the theory VC associated with a complexity class C can prove a given mathematical theorem if the induction hypotheses needed in the proof can be formulated using concepts from C. We are interested in trying to find the weakest class C needed to prove various theorems of interest in computer science. The authors show that weak pigeonhole principle is not provable in theory $VAC^0$ corresponding to $AC^0$ complexity class, but it is provable in $VTC^0$, along with a formula denoting that for every sequence, a sorted sequence exists. Fermat's Little Theorem is not provable in $VPTIME$, condition prime factorization is not in $PTIME$. In the area of bounded arithmetic, Witnessing theorems are studied, which roughly say that if a formula $\forall x \exists y \varphi(x, y)$ is provable in theory $VC$ (for a complexity class $C$), then there exists a function $f$ of complexity $C$ such that $\forall x \varphi(x, f(x))$ is provable in $VC$. So, that we can theoretically extract a real algorithm from a proof of a functional formula! The problem with these theorems are that their proofs typically involve cut elimination theorem or Herbrand's theorem, which say that something is possible to do, but in practice it's not really computationally feasible. As I don't have enough expertise to judge myself, it leads me to thinking that we won't really be able to implement a real code extraction tool from the proofs in these weak logics. My question is: can we actually implement algorithm extraction from a proof of the Witnessing theorem? Maybe I'm wrong in thinking that the current proofs are not convertible to feasible computation? Maybe alternative proofs exist (there are at least 2 for $V^0$ (i.e. $VAC^0$) in the book above), which are computationally feasible? Maybe no feasible proof is known, but theoretically there might exist one? I don't want to list all the technical definitions here, as it would require introducing the two-sorted logic and the bounded arithmetical hierarchy the authors use, which is not strictly essential to this question. But, as an example of a witnessing theorem for AC0: At page 105 (116 of the pdf): Theorem 5.60 (Witnessing Theorem for V0). Suppose that $\varphi (\overrightarrow x, \overrightarrow y, \overrightarrow X, \overrightarrow Y )$ is a $\Sigma^B_0$ formula such that $V^0 \vdash \forall \overrightarrow x \forall \overrightarrow X\exists \overrightarrow y \exists \overrightarrow Y \varphi( \overrightarrow x, \overrightarrow y, \overrightarrow X, \overrightarrow Y )$ Then there are $FAC^0$ functions $f_1, \dots , f_k, F_1, \dots , F_m$ so that $V^0(f_1, \dots , f_k, F_1, \dots , F_m) \vdash \forall \overrightarrow x \forall \overrightarrow X \varphi( \overrightarrow x , \overrightarrow f(\overrightarrow x, \overrightarrow X), \overrightarrow X, \overrightarrow F ( \overrightarrow x, \overrightarrow X)) $

Say $S$ is a connected oriented surface with boundary, and $T$ is a triangulation such that the boundary is a union of simplices. Is it always possible to select simple cycles in $T$ (I mean simple closed paths in the 1-skeleton of $T$) that will be a symplectic basis of $H_{1}(S,\partial S)$? If not, is there an upper bound on how complicated such a basis would be (I mean, say, an upper bound on the sum of coefficients and the lengths of the involved cycles, in terms of the size of the triangulation $T$). Any references would be greatly appreciated. I didn't find a reference for this question of selecting a basis homology that is made out of simple cycles in $T$. I will make do even if there is no boundary involved. Thank you!

Let $ G $ be a finite group and let $ n = |G| $‎. ‎For each divisor $ d $ of $ n $ such that $ 1 < d \leq \sqrt{n} $‎, ‎proceed as follows‎: For every subset $ A \subseteq G $ of size $ d $ that contains the identity element $ 1 $‎, ‎do the following‎: For every subset $ B \subseteq G $ of size $ n/d $ such that‎ $ ‎1 \in B \subseteq \left(G \setminus \left(A^{-1}A\right)\right) \cup \{1\}‎, $ ($A^{-1}A=\{a_1^{-1}a_2:a_1,a_2\in A\}$) ‎proceed to the next step‎: Check whether the Minkowski product satisfies $ G = AB $‎. If such subsets $ A $ and $ B $ can always be found for all valid values of $ d $‎, ‎then print‎: ``G is a CFS group.''. ‎Otherwise‎, ‎print‎: ``G is not a CFS group.'' ‎and also display the group $ G $‎, ‎and the first subset $ A $ (along with its size $ d $) for which the condition $ G = AB $ is not satisfied‎. The following GAP code is written for it (namely, the CFS property): IsCFSGroup := function(G) local n, divs, d, Asets, A, Bsize, Bsets, B, AinverseA, complement, product, success; n := Size(G); divs := Filtered(DivisorsInt(n), d -> d > 1 and d <= Sqrt(n)); for d in divs do Asets := Filtered(Combinations(Elements(G), d), A -> Identity(G) in A); for A in Asets do AinverseA := Set(List(Cartesian(A, A), x -> x[1]^(-1)*x[2])); complement := Difference(Elements(G), AinverseA); AddSet(complement, Identity(G)); # Ensure 1 ∈ B Bsize := n / d; Bsets := Filtered(Combinations(complement, Bsize), B -> Identity(G) in B); success := false; for B in Bsets do product := Set(List(Cartesian(A, B), x -> x[1]*x[2])); if Set(product) = Set(Elements(G)) then success := true; break; fi; od; if not success then Print("G is not a CFS group.\n"); Print("Violating subset A: ", A, "\n"); Print("Size of A (d): ", d, "\n"); return false; fi; od; od; Print("G is a CFS group.\n"); return true; end; But it does not work correctly, e.g., for $S_3$: " G is not a CFS group. Violating subset A: [ (), (1,2,3) ] Size of A (d): 2 false " That is not true. (a) What is wrong with this code (any improvement for it)? (b) Where should it be written in the code if we want to apply one of the following additional conditions? (b1) $A$ or $B$ is a normal subgroup of $G$ (b2) $AB=BA$ Thanks in advance

I'm following "Lecture notes on Differential Geometry" by Chow and Chow. Their treatment of tangent spaces starts with defining a tangent space of a parametrised submanifold $M^n \subset \mathbb{R}^{n+1}$ of Euclidean space. Here is the (slightly rephrased) relevant excerpt: Let $F: U \subset \mathbb{R}^n \rightarrow M^n$ parametrize a relatively open subset $F(U)$ of a submanifold $M^n \subset \mathbb{R}^{n+1}$. Let $\mathbf{u_0} \in U$. Then, by hypothesis, the derivative $dF_{\mathbf{u_0}}: \mathbb{R}^n \rightarrow \mathbb{R}^{n+1}$ is an injective linear map, and may be defined by $$T_{F(\mathbf{u_0})}M^n := d{F_{\mathbf{u_0}}}(\mathbb{R}^n).$$ While this definition makes sense to me in general, I tried applying it to the Euclidean space of dimension $n$ as a submanifold of $\mathbb{R}^{n+1}$. Here is what I have. For $M^n := \mathbb{R}^n$, let $F: \mathbb{R}^n \rightarrow M^n \subset \mathbb{R}^{n+1}$ be defined by $$F(\mathbf{x_0}) = F(x^1, x^2, \ldots, x^n) = (x^1, \ldots, x^n, 0) \in \mathbb{R}^{n+1}$$. Then, the tangent space $$T_{F({\mathbf{x_0})}}M^n = dF_{x_0}(R^n).$$ Then, the RHS is a linear map, given by the $(n+1) \times n$ matrix $$(dF(\mathbb{R}^n))_{ij} = \partial F^i(\mathbb{R^n})/\partial x^j.$$ For any $x \in \mathbb{R}^n$, the RHS of the last expression becomes a diagonal matrix with an extra row of $0$'s in the $(n+1)$th row. Is this correct?