Gilad Chase, Generalized polymorphisms, MSc thesis

detailsabstractBibTeX
## BibTeX

@mastersthesis{Chase2023,,

author = {Gilad Chase},

title = {Generalized polymorphisms},

school = {Technion},

year = {2023}}

copy to clipboard
author = {Gilad Chase},

title = {Generalized polymorphisms},

school = {Technion},

year = {2023}}

We determine all $n$-ary Boolean functions $f_0,\ldots,f_m$ and $m$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation

$f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) =

g_0(f_1(z_{11},\ldots,z_{n1}),\ldots,f_m(z_{1m},\ldots,z_{nm}))$,

for all Boolean inputs ${ z_{ij} : i \in [n], j \in [m] }$. When the functions $f_0,\ldots,f_m,g_0,\ldots,g_n$ satisfy the above, we refer to them as a *generalized polymorphism*. This characterization generalizes a previously known characterization for *polymorphisms*, which are the special case of generalized polymorphisms formed by letting $g_1 = \dots = g_n$.

Our characterization not only captures the previously known characterization of polymorphisms, but also consolidates its case-wise characterization statement into a single consolidated expression. Indeed, this was made possible by viewing polymorphisms in the more general setting of generalized polymorphisms, which revealed a structure previously hidden due to degeneracies imposed by the assumption $g_1 = \dots = g_n$.

The characterization we obtain generalizes the previously known characterization of polymorphisms in two major aspects: first, we show that every generalized polymorphism is essentially composed of an evaluation of an arbitrary Boolean

function $h$ whose inputs are substituted with

$k$ polymorphisms, derived from $k$ disjoint

subsections of the input space. For polymorphisms, this partition degenerates into a singleton, and $h$ degenerates into simply returning the result of the polymorphism, up to sign. We show this aspect of our characterization in isolation, by restricting our inputs to include only functions of degree at least 2. The second aspect in which our characterization generalizes that of polymorphisms is the prevalence of arbitrary evaluations for certain subproblems involving degree 1 functions. For polymorphisms, this type of evaluation occurs in only two types of solutions. In contrast, in our characterization, it permeates throughout all solutions. We show this aspect after showing the first described above, by lifting the degree constraint imposed therein and generalizing the results achieved there using similar methods.

Neta Dafni, Complexity measures on the symmetric group and beyond, MSc thesis

detailsabstractBibTeX
## BibTeX

@mastersthesis{Dafni2022,

author = {Neta Dafni},

title = {Complexity measures on the symmetric group and beyond},

school = {Technion},

year = {2022}}

copy to clipboard
author = {Neta Dafni},

title = {Complexity measures on the symmetric group and beyond},

school = {Technion},

year = {2022}}

The complexity of Boolean functions on the Boolean cube can be measured in several ways, such as circuit complexity and decision tree complexity. Classical results show that many of these measures are polynomially related, such as decision tree complexity, certificate complexity, degree and sensitivity. Recently, the study of Boolean functions has been extended to functions on domains other than the Boolean cube, such as the slice, high-dimensional expanders and the Grassmann scheme. Can the study of different complexity measures can be generalized to some of these domains?

We begin with surveying recent work that generalizes the definitions of some of the classical complexity measures to domains other than the Boolean cube, including the symmetric group, which is our main focus. We then describe results regarding the relations between the different measures, generalizing the classical results and showing that polynomial relations exist between the considered measures for many other domains.

We then focus on functions with low sensitivity, with the goal of constructing efficient circuits for them. First, we generalize a result regarding the existence of small circuits for functions with low sensitivity on the Boolean cube, constructing a circuit of size $n^{O(s)}$, where $s$ is the sensitivity of $f$. Next, we generalize a result regarding the existence of low-depth circuits for functions with low sensitivity on the Boolean cube, and construct such circuits for functions over domains satisfying certain properties, including the symmetric group. Our construction results in an unbounded fan-in circuit of depth $O(s\log n)$ in the case of the symmetric group.

The last part of our work concerns intersecting families of permutations. A family of permutations is $t$-intersecting if any two permutations in the family agree on at least $t$ elements. It is known that for a large enough $n$, the maximal size of a $t$-intersecting family of permutations is $(n-t)!$, and a family of that size is a $t$-star, that is, the set of all permutations mapping some distinct $i_{1},\ldots,i_{t}$ to some distinct $j_{1},\ldots,j_{t}$ respectively. We generalize this result to the case of $t$-setwise-intersection, where any two permutations in the family agree on the image of a set of $t$ elements. We give an alternative proof to a known result stating that for a large enough $n$, the maximal size of a $t$-setwise-intersecting family of permutations is $t!(n-t)!$, and a family of that size is a $t$-setwise-star, that is, the set of all permutations mapping some set $S$ of size $t$ to some $T$ of size $t$. Our proof is much simpler than the known proof (which proves a stronger statement) and works for smaller values of $n$.

Yuval Dagan, Twenty questions game using restricted sets of questions, MSc thesis

detailsabstractBibTeX
## BibTeX

@mastersthesis{Dagan2018,

author = {Yuval Dagan},

title = {Twenty Questions Game Using Restricted Sets of Questions},

school = {Technion},

year = {2018}}

copy to clipboard
author = {Yuval Dagan},

title = {Twenty Questions Game Using Restricted Sets of Questions},

school = {Technion},

year = {2018}}

A basic combinatorial interpretation of Shannon’s entropy function is via the “20 questions” game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution $\pi$ over the numbers $\{1,\ldots,n\}$, and announces it to Bob. She then chooses a number $x$ according to $\pi$, and Bob attempts to identify $x$ using as few Yes/No queries as possible, on average.

An optimal strategy for the “20 questions” game is given by a Huffman code for $\pi$: Bob’s questions reveal the codeword for $x$ bit by bit. This strategy finds $x$ using fewer than $H(\pi)+1$ questions on average. However, the questions asked by Bob could be arbitrary. In this document, we investigate the following question: *Are there restricted sets of questions that match the performance of Huffman codes, either exactly or approximately?*

Our first main result shows that for every distribution $\pi$, Bob has a strategy that uses only questions of the form “$x < c$?” and “$x = c$?”, and uncovers $x$ using at most $H(\pi)+1$ questions on average, matching the performance of Huffman codes in this sense. We also give a natural set of $O(rn^{1/r})$ questions that achieve a performance of at most $H(\pi)+r$, and show that $\Omega(rn^{1/r})$ questions are required to achieve such a guarantee.

Our second main result gives a set $\mathcal{Q}$ of $1.25^{n+o(n)}$ questions such that for every distribution $\pi$, Bob can implement an *optimal* strategy for $\pi$ using only questions from $\mathcal{Q}$. We also show that $1.25^{n-o(n)}$ questions are needed, for infinitely many $n$.

If we allow a small slack of $r$ over the optimal strategy, then roughly $(rn)^{\Theta(1/r)}$ questions are necessary and sufficient.

Yuval Filmus, Hardness of approximating maximum coverage

An exposition of Feige’s hardness proof for Maximum Cover, in its version due to Dana Moshkovitz.

This supplements an older exposition of Feige’s hardness proof for Set Cover, which uses Feige’s original construction.

Yuval Filmus, Kahn–Kalai conjecture: an exposition

detailsabstractBibTeX
## BibTeX

@misc{Filmus22KahnKalai,

title = {Kahn--{K}alai conjecture: an exposition},

author = {Yuval Filmus},

year = {2022}

}

copy to clipboard
title = {Kahn--{K}alai conjecture: an exposition},

author = {Yuval Filmus},

year = {2022}

}

We give an exposition of the recent proof of the Kahn–Kalai conjecture due to Jinyoung Park and Huy Tuan Pham.

Yuval Filmus, Intersecting families are approximately contained in juntas

Our goal in this sketch is to give an exposition of *Independent sets in graph powers are almost contained in juntas* by Dinur, Friedgut and Regev, as applied to intersecting families by Dinur and Friedgut in *Intersecting families are essentially contained in juntas*.

Yuval Filmus, Berge's theorem on ideals of sets

Berge *(A theorem related to the Chvátal* conjecture) showed that if $\mathcal{F}$ is a downwards-closed family of sets, then either $\mathcal{F}$ or $\mathcal{F} \setminus \{\emptyset\}$ can be partitioned into pairs of disjoint sets.

We reproduce a proof here. For another account, see Section 2.1 of Embla Klingberg, A note on Chvátal’s conjecture.

Yuval Filmus, Harper's isoperimetric inequality

An exposition of Harper’s proof of his edge isoperimetric inequality for the hypercube, following his book *Global methods for combinatorial isoperimetric problems*.

The proof uses a generalization of shifting that Harper calls *compression*.

Compared to Harper’s original proof (also reproduced in the book), the compression proof includes only one simple calculation.

Yuval Filmus, Forcing with random variables and proof complexity

An exposition of parts of Jan Krajíček’s book Forcing with random variables and proof complexity, concentrating on lower bounds for constant depth proof systems.

Parts of this exposition has been given as talks in a reading group on the book on 13/6/2013 and 20/6/2013.

Yuval Filmus, Reckhow's theorem

We given an exposition of Reckhow’s theorem from his thesis, which extends Spira’s formula balancing to Frege proofs. This balancing theorem, which doesn’t appear explicitly in the thesis, is essential for showing that all Frege proofs are p-equivalent, one of the main results of the thesis.

An alternative exposition can be found in Krajíček’s monograph Bounded Arithmetic, Propositional Logic and Complexity Theory.

Yuval Filmus, Smolensky's polynomial method

We give an exposition of Smolensky’s fundamental paper on the polynomial method, a lower bound method in circuit complexity. Books usually contain a simpler argument which works only for parity, whereas Smolensky’s argument also works for majority (directly). Our exposition omits the step of approximating a constant depth circuit by a low-degree polynomial.

Yuval Filmus, Submodular maximization

We survey several recent algorithmic results on submodular maximization:

- The greedy algorithm for monotone submodular maximization over uniform matroids.
- The continuous greedy algorithm for monotone submodular maximization over arbitrary matroids (Calinescu, Chekuri, Pál and Vondrák).
- The non-oblivious local search algorithm for monotone submodular maximization over arbitrary matroids (Filmus and Ward).
- Uncostrained non-monotone submodular maximization (Buchbinder, Feldman, Naor and Schwartz).

We also briefly survey some lower bounds:

- $1-1/e$ NP-hardness for maximum coverage (Feige).
- $1-1/e$ value oracle hardness for monotone submodular maximization over a uniform matroid (Nemhauser and Wolsey).
- $1/2$ value oracle hardness for unconstrained submodular maximization (Feige, Mirrokni and Vondrák).
- The symmetry gap method (Vondrák, Dobzinski and Vondrák).

This talk was given at the Toronto Student Seminar on 31/1/2013.

Yuval Filmus, Permanent is hard to compute even on a good day

Cai, Pavan and Sivakumar showed that it is hard to compute the permanent even with an inversely polynomial success probability, assuming the *worst-case* hardness of computing the permanent. Their proof combines the LFKN protocol with Sudan’s list-decoding algorithm for Reed-Solomon codes. We given an exposition of their result, as well as several results leading to it.

This talk was given at the Toronto Student Seminar on 17/9/2012.

Yuval Filmus, Matrix multiplication

An exposition on algorithms for matrix multiplication, in two parts:

- Part 1:
- The arithmetic model.
- Bilinear normal form for matrix multiplication.
- Tensor notation and tensor rank.
- Border rank.
- Schönhage’s $\tau$ theorem (the asymptotic sum inequality).
- Coppersmith’s $\tilde{O}(n^2)$ algorithm for multiplying rectangular matrices.

- Part 2:
- The laser method.
- The Coppersmith–Winograd algorithms.
- Capacity: the fundamental combinatorial underpinning of the Coppersmith–Winograd method.

These talks were given in the Toronto Student Seminar on 2/2/2012 and 9/2/2012, though the second one has been significantly updated since.

The talks were given again in the IAS theory seminar, on 25/2/2014 and 4/3/2014. The second part has been significantly updated: the combinatorial construction has been simplified following Davie and Stothers, and the general presentation follows Le Gall’s recent paper.

Yuval Filmus, Hardness of approximating set cover

An exposition of Feige’s celebrated result on the hardness of approximating set cover.

This talk was given as part of the PCP reading group on 23/1/2010.

See also an exposition of the hardness of maximum coverage, the dual problem, which uses the modern proof due to Dana Moshkovitz.

Yuval Filmus, Two proofs of the central limit theorem

We provide two proofs of the central limit theorem (up to Lévy’s continuity theorem), one using cumulants and the other using moments. As a bonus, we also prove the asymptotic normality of the number of distinct prime factors of a ‘random’ integer. Our account follows the exposition in the book The semicircle law, free random variables and entropy.

This talk was given at the Toronto Student Seminar on 20/1/2010.

Yuval Filmus, Modern integer factorization methods

We survey several modern integer factorization methods, including Pollard’s $\rho$, Pollard’s $p-1$, Williams’ $p+1$, the elliptic curve method, Shanks’ continued fractions algorithm, the quadratic sieve (including MPQS and Dixon’s provable variant) and the number-field sieve (which is only sketched).

Originally given as a talk in the Toronto Student Seminar on 25/11/2009, this talk proved popular and I have given it several more times.

Yuval Filmus, Seven trees in one

Andreas Blass explained how the type-theoretic identity $T=1+T^2$ for binary trees leads to a “finitistic” identity $T^7=T$ (the solution to the former equation is a primitive sixth root of unity). More generally, he proved that two polynomials in *$T$* are “equal” (under his finitistic interpretation) if and only if they agree on a primitive sixth root of unity and in terms of cardinalities. We give an exposition of this result (using work by Fiore and Leinster), using a more intuitive definition of “strong” equality, as equality given by an algorithm which also works for infinite binary trees.

This talk was given at the Toronto Student Seminar on 16/9/2009.

Yuval Filmus, Quadratic Boolean functions on the cube

detailsabstractBibTeX
## BibTeX

@misc{Filmus22quad,

title = {Quadratic {B}oolean functions on the cube},

author = {Yuval Filmus},

howpublished = {Online note},

year = {2022}

}

copy to clipboard
title = {Quadratic {B}oolean functions on the cube},

author = {Yuval Filmus},

howpublished = {Online note},

year = {2022}

}

We give a complete list of all Boolean degree 2 functions on the Boolean cube.

Yuval Filmus, A simple proof of the Kindler–Safra theorem

detailsabstractBibTeX
## BibTeX

@misc{FilmusKS,

title = {A simple proof of the {K}indler--{S}afra theorem},

author = {Yuval Filmus},

year = {2022},

howpublished = {Manuscript}

}

copy to clipboard
title = {A simple proof of the {K}indler--{S}afra theorem},

author = {Yuval Filmus},

year = {2022},

howpublished = {Manuscript}

}

We give a new proof of the Kindler–Safra theorem, using the invariance principle.

Yuval Filmus and Nathan Lindzey, Murali's basis for the slice

The slice consists of all vectors $(x_1,\ldots,x_n) \in \{0,1\}^n$ of Hamming weight $k$. We usually assume that $k \leq n/2$.

My paper constructs an explicit orthogonal basis for functions on the slice. The basis is canonical in a sense made clear by Murali K. Srinivasan, who had given an inductive construction for the same basis in his own paper.

In this short note, we first show how Murali’s inductive construction gives rise to the explicit formula appearing in my paper. Then, we briefly give yet another construction of the basis, using the Gram–Schmidt process.

Yuval Filmus, One-step modified log Sobolev on the complete complex

Cryan, Guo and Moussa, *Modified log-Sobolev inequalities for strongly log-concave distributions*, proved a log-Sobolev inequality for high-dimensional expanders.

We give a simplified proof for the complete complex.

Yuval Filmus, Information complexity of AND

We show that the information complexity of the AND function with respect to the distribution $\mu(0,0)=\mu(0,1)=\mu(1,0)=1/3$ is strictly positive for any worst-case error rate (strictly less than $1/2$).

Using this, a simple (but tricky) argument using the chain rule shows that the information complexity of set disjointness is $\Omega(n)$ for any worst-case error rate, which implies that the randomized communication complexity of set disjointness is $\Omega(n)$.

Yuval Filmus, NPN equivalence classes of Boolean functions

Two Boolean functions are NPN-equivalent if they can be reached from one another by permuting the inputs, negating some of the inputs, and possibly negating the output. The number of different equivalence classes for a given number of variables forms the sequence A000370, which starts 2, 4, 14, 222, 616126, for functions of 1 to 5 variables, respectively.

For $n$ up to 5, we have compiled a list of all NPN-equivalence classes of Boolean functions on $n$ variables. Each such function is given as a hexadecimal integer in which bit $i$ is the value at the $i$th input.

Yuval Filmus, Antichains on the Boolean lattice of dimension 6

We provide a list of all inequivalent non-trival antichains on the Boolean lattice of dimension 6, excluding the empty antichain and the one containing the empty set. Alternatively, this is a list containing all inequivalent non-constant monotone Boolean functions on six inputs, given by their minterms.

Antichains depending of dimension $n$ are given in terms of the points $1,\ldots,n$. The number of antichains of given dimension (including the two trivial cases) forms the sequence A003182.

Yuval Filmus, Khintchine–Kahane using Fourier analysis

Latała and Oleszkiewicz proved the special $L_1$ case of the Khintchine–Kahane inequality. We reformulate their proof using Fourier analysis.

Yuval Filmus, Triangle-intersecting families of graphs on eight vertices

We given a Katona-like proof that a triangle-intersecting family of graphs contains at most 1/8 of the graphs. Unfortunately, our proof works only on up to eight vertices. We discuss several other methods which also cannot give a general proof.

Parts of this note are summarized in my thesis.

Yuval Filmus, Regular languages closed under Kleene plus

Vincenzo Ciancia asked on cstheory.stackexchange about the class of regular languages satisfying the following property: whenever a word $w$ belongs to the language, all of its positive powers $w^k$ also belong to the language. He termed these languages ‘circular languages’. Answering his question, we have shown the following:

- Every circular language can be written as the union of expressions $r^+$. We exhibit a language where this union cannot be disjoint.
- Given a DFA for a regular language, it is PSPACE-complete to decide whether the language is circular.

The normal form appears in a paper by Calbrix and Nivat, and the PSPACE-completeness result follows quite easily from a paper by Kozen, as I detail in my answer. My proofs appear below.

Yuval Filmus, Proof of the $p$-biased version of the Erdős–Ko–Rado theorem using Katona's method

Katona gave a simple proof of the Erdős–Ko–Rado theorem. We adapt his proof to the $\mu_p$ setting. We are also able to prove uniqueness, but not stability.

Yuval Filmus, Thirteenth proof of a result about tiling a rectangle

Stan Wagon gave fourteen proofs of the following result about tiling a rectangle: if a rectangle can be tiled using rectangles with at least one integral side, then the tiled rectangle also has at least one integral side. We paraphrase his 13th proof.

Yuval Filmus, Self-avoiding walks on the integers which move at most two integers at a time

Yaroslav Bulatov asked on mathoverflow what is the asymptotic number of self-avoiding integer walks of length $n$ in which adjacent positions are either 1 or 2 apart. We obtain a formula for the exact number of such walks, and deduce that it is $\tilde{O}(\mu^n)$, where $\mu \approx 2.20556943040059$.

Yuval Filmus, Range of symmetric matrices mod 2

Yuval Filmus, On the number of NOT gates needed to invert n inputs

We solve the following puzzle: given an arbitrary supply of AND gates and OR gates, invert $n$ inputs using as few NOT gates as possible.

Yuval Filmus, On the sequence $n$ mod $x$

Avinoam Braverman considered the sequence $n \bmod x$, where $1 \leq x \leq \sqrt{n}$, took its local minima, and plotted the results. When $n$ is large, a curious pattern composed out of what seem to be triangles appears. We explain this phenomenon heuristically, given formulas for the envelope of the “triangles” (which turn out to be quadratic functions). We go on to describe the envelope of the plot when an arbitrary number of the local minima and local maxima operations are composed.

Yuval Filmus, Permutations avoiding patterns of length 3

We provide a bijective proof for the well-known fact that the number of 123-avoiding permutations and the number of 132-avoiding permutations are both counted by Catalan numbers. Simion and Schmidt came up with a direct bijection between the two sets of permutations, and their proof is recommended over mine.

Yuval Filmus, Equivalent definitions of the Sprague–Grundy function

We prove that several equivalent definitions of the Sprague–Grundy function coincide (an exercise given in a course on combinatorial games given by Aviezri Fraenkel).

Yuval Filmus, Examples of the GCD proof system

If $(x,y)=1$ then $(x+y,xy)=1$. The first part shows how to prove this using standard arguments and using the characterization of GCD as the minimal positive value obtained as an integer combination of the operands. The second part generalizes the argument to a lemma involving $n$ variables.

Yuval Filmus, Until cannot be expressed using Next, Always, Eventually

It is well-known that the *until* operator in linear temporal logic (LTL) cannot be expressed using *next*, *always* and *eventually*. We provide a simple proof of this fact.

Yuval Filmus, Orthogonal matrices with optimal $L_2$ norm

Question 8 in Chapter 2 of *The Probabilistic Method* asks us to show that for every $n\times n$ orthogonal matrix and $1\leq k\leq n$, there is a column such that the squared $L_2$ norm of its first $k$ entries is at least $k/n$, or at most $k/n$. It also asks for an example in which this is tight. We exhibit such an example which works simultaneously for all $k$.

Yuval Filmus, Largest adjacent segments on the unit circle

Suppose $n$ points are thrown on the circumference of a unit-circumference circle, partitioning the circumference into $n$ segments. What is the expected length of the $k$th smallest segment? There is a well-known formula for this expectation.

We consider the expected length of $k$th smallest two adjacent segments. We develop a method for computing them exactly, and compute the expectations for several small $n,k$. The results do not seem to fit into a nice pattern.

Yuval Filmus, A positive proof of Dehn's theorem

Dehn proved that if a rectangle can be tiled by rectangles whose sides are commensurable, then the tiled rectangle is also commensurable. His proof, as described in *Proofs from the book*, applies a homomorphism which results in possibly negative side lengths. We modify his proof so that all side lengths are positive.

The crucial ingredient is the following lemma: for each finite set of positive reals there is a basis (over the rationals) of positive reals such that every element in the set is a non-negative integral combination of base elements. We provide two proofs of this lemma, one due to us and one due to Avinoam Braverman.

Yuval Filmus, A combinatorial interpretation for the product of two geometric series in independent variables

We give a combinatorial proof of the identity $\frac{1}{1-x} \cdot \frac{1}{1-y} = \frac{1}{1-x-y+xy}$.

Yuval Filmus, Riddle concerning $\pm1$ vectors

A big sheet of paper contains $2^n$ rows consisting of all possible vectors of length $n$ whose entries are $+1$ or $-1$. Someone changes some of the entries to zero. Show that there must be a non-empty subset of the rows summing to zero.

Probably much harder than you think it is!

Alex Wilkie, Wilkie's proof of the switching lemma

Excerpt from *Modèles non-standard en arithmétique et théorie des ensembles*, Jean-Pierre Ressayre & Alec J. Wilkie.

McKay's easy proof of Cauchy's theorem in group theory

Another proof of Cauchy’s theorem, *American Mathematical Monthly*, Vol. 66 (February 1959), p. 119.

Adolf Hurwitz, Hurwitz's proof that four-square-like identities only occur in dimensions 1,2,4,8

Über die Komposition der quadratischen Formen von beliebig vielen Variablen, *Nachrichten von der k. Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-physikalische Klasse*, 1898, S. 309–316.

Adolf Hurwitz, Hurwitz's proof of the transcendence of $e$

Beweis der Transzendenz der Zahl $e$, *Mathematische Annalen*, Bd. 43, 1893, S. 220–221.

Translation from Herstein’s *Topics in Algebra*, p. 176–178.

Paul Gordan, Gordan's proof of the transcendence of $e$ and $\pi$

Transcendenz von $e$ und $\pi$, *Mathematische Annalen*, Bd. 43, 1893, S. 222–224.

David Hilbert, Hilbert's proof of the transcendence of $e$ and $\pi$

Über die Transzendenz der Zahlen $e$ und $pi$, *Mathematische Annalen*, Bd. 43, 1893, S. 216–219.

Joseph-Louis Lagrange, Lagrange's proof of Wilson's theorem

Démonstration d’un Théorème nouveau concernant les Nombres premiers, *Nouveaux Mémoires de l’Académie royale des Science et Belles-Lettres de Berlin*, année 1771.

Joseph-Louis Lagrange, Lagrange's proof of the four square theorem

Démonstration d’un Théorème d’Arithmétique, *Nouveaux Mémoires de l’Académie royale des Science et Belles-Lettres de Berlin*, année 1770.