International audience

We present the "ProofWidgets" framework for implementing general user interfaces (UIs) within an interactive theorem prover. The framework uses web technology and functional reactive programming, as well as metaprogramming features of advanced interactive theorem proving (ITP) systems to allow users to create arbitrary interactive UIs for representing the goal state. Users of the framework can create GUIs declaratively within the ITP’s metaprogramming language, without having to develop in multiple languages and without coordinated changes across multiple projects, which improves development time for new designs of UI. The ProofWidgets framework also allows UIs to make use of the full context of the theorem prover and the specialised libraries that ITPs offer, such as methods for dealing with expressions and tactics. The framework includes an extensible structured pretty-printing engine that enables advanced interaction with expressions such as interactive term rewriting. We exemplify the framework with an implementation for the https://leanprover-community.github.io. The framework is already in use by hundreds of contributors to the Lean mathematical library.

Let $G$ be the special linear group ${SL}(2,q)$. We show that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are sampled uniformly from large subsets $A$ and $B$ of $G^t$, then their interleaved product $a_1 b_1 a_2 b_2 \cdots a_t b_t$ is nearly uniform over $G$. This extends a result of the first author [W. T. Gowers, Combin. Probab. Comput., 17 (2008), pp. 363--387], which corresponds to the independent case where $A$ and $B$ are product sets. We obtain a number of other results. For example, we show that if $X$ is a probability distribution on $G^m$ such that any two coordinates are uniform in $G^2$, then a pointwise product of $s$ independent copies of $X$ is nearly uniform in $G^m$, where $s$ depends on $m$ only. Extensions to other groups are also discussed. We obtain closely related results in communication complexity, which is the setting where some of these questions were first asked by Miles and Viola [ Shielding circuits with groups, in ACM Symposium on the Theory of Computing (STOC), ACM, New York, 2013, pp. 251--260]. For example, suppose party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of elements from $G$. The parties are promised that the interleaved product $a_{11}\dots a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is equal either to the identity $e$ or to some other fixed element $g\in G$, and their goal is to determine which of the two the product is equal to. We show that for all fixed $k$ and all sufficiently large $t$ the communication is $\Omega(t \log |G|)$, which is tight. Even for $k=2$ the previous best lower bound was $\Omega(t)$. As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola [ Shielding circuits with groups, in ACM Symposium on the Theory of Computing (STOC), ACM, New York, 2013, pp. 251--260] in the “only computation leaks” model.

This paper describes a program that solves elementary mathematical problems, mostly in metric space theory, and presents solutions that are hard to distinguish from solutions that might be written by human mathematicians.

Party Aiof k parties A1,...,Akreceives on its forehead a t-tuple (ai1,...,ait) of elements from the group G = SL(2, q). The parties are promised that the interleaved product a11...ak1a12...ak2...a1t...aktis equal either to the identity e or to some other fixed element g ∈ G. Their goal is to determine which of e and g the interleaved product is equal to, using the least amount of communication. We show that for all fixed k and all sufficiently large t the communication is Ω(t log |G|), which is tight. As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola (STOC 2013) in the "only computation leaks" model. Our main technical contribution is of independent interest. We show that if X is a probability distribution on Gmsuch that any two coordinates are uniform in G2, then a pointwise product of s independent copies of X is nearly uniform in Gm, where s depends on m only.

Alice receives a tuple (a1,...,at) of t elements from the group G = SL(2,q). Bob similarly receives a tuple of t elements (b1,...,bt). They are promised that the interleaved product prodi ≤ t ai bi equals to either g and h, for two fixed elements g,h ∈ G. Their task is to decide which is the case.