University of Luxembourg Maciej Skorski <ccs2012> <concept>
<concept_id>10002950.10003648.10003671</concept_id> <concept_desc>Mathematics
of computing Probabilistic algorithms</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Mathematics of computing Probabilistic algorithms John Q. Open and Joan
R. Access 2 December 24–27, 2016 Little Whinging, United Kingdom

# Modern Analysis of Sparse Random Projections

Maciej Skorski

###### Abstract

There has been recently a lot of research on sparse variants of random
projections, faster adaptations of the state-of-the-art dimensionality
reduction technique originally due to Johsnon and Lindenstrauss. Although the
construction is very simple, its analyses are notoriously complicated. Meeting
the demand for both simplicity and accuracy, this work establishes sharp sub-
poissonian tail bounds for the distribution of sparse random projections.
Compared to other works, this analysis provide superior numerical guarantees
(exactly matching impossibility results) while being arguably less complicated
(the technique resembles Bennet’s Inequality and is of independent interest).

###### keywords:

Sparse Random Projections, Johnson-Lindenstrauss Lemma, Poisson Tails

###### category:

##  1 Introduction

###  1.1 Contribution

Random linear projections have the extremely attractive property of
considerably _reducing dimensionality_ of data while being _nearly isometric_.
This fact together with provable guarantees, shown for the first time by
Johnson and Lindenstrauss [6], make them the state-of-the-art preprocessing
technique for data science tasks and the focus of intensive research in high-
dimensional statistics. More recently, there has been lots of works studying
_Sparse Johnson-Lindestrauss Transforms_ [5, 8, 1, 9, 3, 4], in order to speed
up computations.

The purpose of this work is to give a novel analysis of Sparse Johnson-
Lindestrauss Transforms, which is _simple and accurate_ at the same time. To
this end, we re-analyze the sparse construction due to Kane [9], which builds
on randomly sparsifying Rademacher matrices offers best known dimension-
quality tradeoffs. Our main result reads as follows:

######  Theorem 1.1 (Poisson Tails of Sparse Johnson-Lindenstrauss Lemma).

For any confidence $\delta>0$, distortion $\epsilon>0$ and integer sparsity
$s>0$, there is a random $m\times n$ matrix $A$ with $p=\frac{s}{m}$ fraction
of non-zero elements in each row, such that the nearly isometric property:

$\displaystyle\mathbf{P}\left\\{(1-\epsilon)\|x\|^{2}\leqslant\|Ax\|^{2}\leqslant(1+\epsilon)\|x\|^{2}\right\\}\geqslant
1-\delta,$ (1)

holds for any vector $x$, provided that the embedding dimension is at least

$\displaystyle m\geqslant\frac{4\log(2/\delta)}{\epsilon^{2}}\cdot
h\left(\frac{25\epsilon}{p}\right)^{-1},$ (2)

and that $p\leqslant\frac{1}{30},\epsilon\leqslant p\log(1/2p)$, where $h$ is
the "Bennet function" defined as

$\displaystyle h(u)\triangleq\frac{(1+u)\log(1+u)-u}{u^{2}/2}.$ (3)

The construction of the matrix $A$ is presented in Algorithm 1.

SparseJLT  _$(n,m,p)$_

inputs : data dimension $n$, embedding dimension $m$, sparsity $s$.

output : sparse projection $m\times n$ matrix $A$.

foreach  _column $i\in\\{1\ldots m\\}$_ do

$A_{i}\leftarrow$ sparse column of length $n$ with non-zero entries at $s$
random positions and values randomly chosen from $\pm\frac{1}{\sqrt{s}}$.

end foreach

return _$A=[A_{1}\ldots A_{m}]$_

Algorithm 1 Construction of Sparse Johnson-Lindenstrauss Transform

The property (1) is the standard formulation of the Johnson-Lindenstrauss
Lemma (sometimes the result is presented as a union bound over multiple
vectors $x$). Intuitively, it ensures the small relative change in the vector
length (controlled by $\epsilon$) with high confidence ($\delta$ is the
failure probability). The sparsity parameter $p$ is ideally kept possibly
small, however the price is a loss in quality (bigger distortion, higher
dimension or lower confidence).

###  1.2 Comparison to Related Works

We now discuss how our result improves upon bounds available in the existing
literature.

  1. 1.

The result offers a valuable and elegant explanation of the tails in the
sparse Johnson-Lindenstrauss Lemma: they are dominated by a Poisson
distribution (the term $h$ is typical for Bennet’s trick and Poissonian tail
bounds). The proof is elementary and short.

  2. 2.

In the regime $\epsilon/p\to 0$, the bound exactly matches the best possible
dimension for the Johnson-Lindenstrauss Lemma, found recently by Burr at al.
[2] (we then have $m=\frac{4\log(2/\delta)}{\epsilon^{2}}\cdot(1+o(1))$). This
is a surprisingly strong result, as before we only knew that it approaches the
optimal dimension up to a large constant factor (and the exponentially large
gap loss in the confidence). In other words, this paper shows for the first
time that sparse random projections can be on pair with their dense
(unrestricted) counterparts.

  3. 3.

In the regime $\epsilon=\Theta(p)$ our bound shows that it is possible to
choose $m=O(\frac{\log(2/\delta)}{\epsilon^{2}})$, which gives the sparsity
$s=O(\epsilon^{-1})$. This is consistent with the literature, but our analysis
gives much better constants (best explicit constants were due to Cohen at. al.
[4])

  4. 4.

In the regime $\epsilon/p\gg 0$ our bound offers an interesting dimension-
sparsity tradeoff. Namely, we can have
$m=\frac{4B\log^{-1}B\log(2/\delta)}{\epsilon^{2}}$ and
$s=O(\epsilon^{-1}/\log B)$. In other words, we can improve the sparsity by a
factor, but loose exponentially in the dimension. Such a result appears only
in one work, a somewhat complicated analysis due to Cohen [3]. The result
above is more elementary and provides explicit and better constants. It also
appears to be asymptotically better, namely in [3] we find a bound on $m$
worse by $\log B$.

Bounds from related works, (also the dimension optimallity), are covered in
detail in Table 1.

Author | Bounds | Analysis
---|---|---
[7] | $m\leqslant O\left(\frac{4\log(2/\delta)}{\epsilon^{-2}}\right)$ | Lower Bounds
[2] | $m\leqslant\frac{4\log(2/\delta)(1+o(1))}{\epsilon^{-2}},\ \epsilon\to 0$ | Lower Bounds
[8] | $m\geqslant\Omega(1)\max\left\\{\frac{\log(2/\delta)}{\epsilon^{2}},\frac{\log^{2}(2/\delta)}{p\epsilon}\right\\}$ | Use of Rademacher Chaos Bounds
[8] | $m\geqslant\Omega(1)\max\left\\{\frac{\log(2/\delta)}{\epsilon^{2}},\frac{\log^{2}(1/\delta)\frac{\log\log\log(2/\delta)}{\log\log(2/\delta)}}{p\epsilon}\right\\}$ | Moment Bounds by Graphs Enumeration
[9] | $m\geqslant\Omega(1)\max\left\\{\frac{\log(2/\delta)}{\epsilon^{2}},\frac{\log(2/\delta)}{p\epsilon}\right\\}$ | Moment Bounds by Graphs Enumeration
[3] | $m\geqslant\Omega(1)\max\left\\{\frac{B\log(2/\delta)}{\epsilon^{2}},\frac{\log_{B}(2/\delta)}{p\epsilon}\right\\},\textrm{any }B>2$ | Matrix Chernoff Bounds + Majorization Arguments
[4] | $m\geqslant\Omega(1)\max\left\\{\frac{\log(2/\delta)}{\epsilon^{2}},\frac{\log(2/\delta)}{p\epsilon}\right\\}$ | Hanson-Wright Lemma + Random Matrix Bounds
[4] | $m\geqslant\max\left\\{\frac{128\log(1/\delta)}{\epsilon^{2}},\frac{8\sqrt{2}\log(2/\delta)}{p\epsilon}\right\\}$ | Decoupling + Bounding MGF
this work | $m\geqslant\frac{4\log(2/\delta)}{\epsilon^{2}}\cdot h\left(\frac{25\epsilon}{p}\right)^{-1},\quad\epsilon\leqslant p\log(1/2p)$ | Bennet’s Technique

Table 1: Bounds for Sparse JL Transforms. It is assumed that $p$ is
sufficiently small, e.g. $p<\frac{1}{30}$.

##  2 Preliminaries

The standard way of obtaining tail bounds is the Crammer-Chernoff inequality
$\mathbf{P}\\{X\geqslant\epsilon\\}\leqslant\mathrm{e}^{-s\epsilon}\mathbf{E}\mathrm{e}^{sX}$,
to be optimized over $s>0$ (Markov’s inequality applied to exponential
moments).

Recall that the Poisson random variable follows the distribution
$\mathbf{P}\\{\mathsf{Poiss}(\lambda)=k\\}=\mathrm{e}^{-\lambda}\lambda^{k}/k!$.
We have
$\mathbf{E}\mathrm{e}^{s\mathsf{Poiss}(\lambda)}=\mathrm{e}^{\lambda(\mathrm{e}^{t}-1)}$
and the Crammer-Chernoff method gives

######  Lemma 2.1 ([10]).

For any $\lambda>0$ and $\epsilon>0$ we have that
$\mathbf{P}\left\\{\mathsf{Poiss}(\lambda)\geqslant\epsilon\right\\}\leqslant\mathrm{e}^{-\lambda}(\mathrm{e}\lambda/\epsilon)^{\epsilon}$.

##  3 Proof of Theorem 1.1

###  3.1 Step 1: Decomposition over Embedding Dimension

Let $A$ be as in Algorithm 1. By the identity $\|y\|^{2}=y^{T}y$ we obtain

$\displaystyle\|Ax\|^{2}-\|x\|^{2}=x^{T}Bx,\quad B\triangleq A^{T}A-I.$ (4)

We see that $B$ is off-diagonal, because $\sum_{k}A_{i,k}^{2}=1$ ($A$ has
exactly $s$ entries of absolute value $1/\sqrt{s}$ in each column). Let
$\eta_{i,j}$ indicate if the row $i$ is selected when constructing the column
$j$ in Algorithm 1 and let $r_{i,j}$ be independent Rademacher random
variables. Then:

$\displaystyle
B=\sum_{k}B_{k},\quad(B_{k})_{i,j}=\begin{cases}\frac{1}{s}\eta_{k,i}\eta_{k,j}r_{k,i}r_{k,j}&i\not=j\\\
0&i=j\end{cases}.$ (5)

Observe that $B_{k}$ are not independent, because $\eta_{k,i}$ are not
independent across rows $k$. Nevertheless, one can show the following _iid
majorization_ :

$\displaystyle
0\leqslant\mathbf{E}(x^{T}\sum_{k}B_{k}x)^{q}\leqslant\mathbf{E}(x^{T}\sum_{k}B^{\prime}_{k}x)^{q},$
(6)

where $(B^{\prime}_{k})$ are independent and distributed as $(B_{k})$. Indeed,
$B^{\prime}_{k}$ is be constructed by replacing $\eta_{k,i}$ that appear in
$B_{k}$ by independent Bernoulli random variables $\eta^{\prime}_{k,i}$. By
expanding both sides into sums of monomials and the symmetry of $r_{k,i}$ we
see that it suffices to prove

$\displaystyle 0\leqslant\mathbf{E}\prod_{(k,i)\in
S}\eta_{k,i}^{d_{k,i}}x_{i}^{d_{k,i}}\leqslant\mathbf{E}\prod_{(k,i)\in
S}{\eta^{\prime}}_{k,i}^{d_{k,i}}x_{i}^{d_{k,i}},$ (7)

for any set of tuples $S$ and even exponents $d_{k,i}$. Now the first
inequality follows as $d_{k,i}$ are even, while the second reduces to
$\mathbf{E}\prod_{i\in I}\eta_{k,i}\leqslant\mathbf{E}\prod_{i\in
I}{\eta}^{\prime}_{k,i}$ for any fixed $k$ and any set $I$ (because
$\eta^{\prime}_{k,i}$ are independent for different $k$), which simply means
that sampling with replacement makes hitting any set $I$ less likely than
independent sampling - obviously true.

We now see that the problem reduces to analyzing

$\displaystyle Z=\sum_{i\not=j}x_{i}x_{j}\eta_{i}\eta_{j}r_{i}r_{j},$ (8)

because from Equation 6 we have the following bound on exponential moments:

$\displaystyle\mathbf{E}\mathrm{e}^{tx^{T}Bx}\leqslant\mathbf{E}\mathrm{e}^{|t|\sum_{k}x^{T}{B^{\prime}}_{k}x}=\mathbf{E}\mathrm{e}^{t\cdot\frac{Z_{1}+\cdots+Z_{m}}{s}},\quad
Z_{i}\sim^{iid}Z.$ (9)

###  3.2 Step 2: Moments of 1-Dim Dense Random Projections

We first observe that for any sequence of real numbers $(y_{i})$ and any
positive integer $q$

$\displaystyle(\sum_{i\not=j}y_{i}y_{j})^{q}\leqslant(\sum_{i}y_{i})^{2q}.$
(10)

Indeed, if we replace $y_{i}$ by $|y_{i}|$ the left side can only increase
while the right-hand side doesn’t change; for non-negative $y_{i}$ the
inequality follows as $\sum_{i\not=i}y_{i}y_{j}\leqslant(\sum_{i}y_{i})^{2}$.
Hence,

$\displaystyle\mathbf{E}[Z^{q}]\leqslant\mathbf{E}(\sum_{i}x_{i}\eta_{i}r_{i})^{2q}.$
(11)

By the multinomial expansion and the symmetry

$\displaystyle\mathbf{E}(\sum_{i}x_{i}^{2}\eta_{i})^{2q}=\sum_{r=2}^{q}p^{r}\sum_{d_{1},\ldots,d_{r}\in\mathbb{Z}^{+}}\binom{2q}{2d_{1},\ldots,2d_{r}}\sum_{i_{1}\not=i_{2}\not=\cdots\not=i_{r}}x_{i_{1}}^{2d_{1}}\cdots
x_{i_{r}}^{2d_{r}}.$ (12)

Furthermore, for every $d_{1},\ldots,d_{r}\in\mathbb{Z}^{+}$ such that
$\sum_{i}d_{i}=q$ it follows that

$\displaystyle\sum_{i_{1}\not=i_{2}\not=\cdots\not=i_{r}}x_{i_{1}}^{2d_{1}}\cdots
x_{i_{r}}^{2d_{r}}\leqslant\binom{q}{d_{1},\ldots,d_{r}}^{-1}(\sum_{i}x_{i}^{2})^{q},$
(13)

by keeping only the terms $x_{i_{1}}^{2d_{1}}\cdots x_{i_{r}}^{2d_{r}}$ from
the expansion of the right side.

By combining the last three inequalities and $\sum_{i}x_{i}^{2}=1$ we obtain

$\displaystyle\mathbf{E}[Z^{q}]\leqslant\sum_{r=2}^{q}p^{r}\sum_{d_{1},\ldots,d_{r}\in\mathbb{Z}^{+}}\binom{2q}{2d_{1},\ldots,2d_{r}}\binom{q}{d_{1},\ldots,d_{r}}^{-1}.$
(14)

To simplify the sum, we will use the following bound

$\displaystyle\binom{2q}{2d_{1},\ldots,2d_{r}}\leqslant
2^{q}\cdot\binom{q}{d_{1},\ldots,d_{r}}^{2},\quad
d_{1},\ldots,d_{r}\in\mathbb{Z}^{+},d_{1}+\cdots+d_{r}=q.$ (15)

The inequality is equivalent to $\binom{2q}{q}\leqslant
2^{q}\prod_{i=1}^{r}\binom{2d_{i}}{d_{i}}$. Let $B_{k}=\binom{2k}{k}$ be the
central binomial coefficient; the relation $B_{k}/B_{k-1}=4\cdot(1-1/2k)$ and
the bound $1-\frac{1}{2k}\geqslant\frac{1}{2}$ imply $B_{k}\geqslant 2^{k}$.
Then $2^{q}\prod\binom{2d_{i}}{d_{i}}\geqslant 2^{q}\cdot
2^{d_{1}+\cdots+d_{r}}=2^{2q}\geqslant\binom{2q}{q}$, so the claim follows.

This bound, together with
$\sum_{d_{1},\ldots,d_{r}\in\mathbb{Z}^{+}}\binom{q}{d_{1},\ldots,d_{r}}\leqslant(1+\cdots+1)^{q}=r^{q}$
implies

$\displaystyle\mathbf{E}[Z^{q}]\leqslant 2^{q}\sum_{r=2}^{q}p^{r}r^{q}.$ (16)

###  3.3 Step 3: Poisson Majorization

Using Equation 16 for $q\geqslant 3$ and the more accurate bound
$\mathbf{E}[Z^{q}]\leqslant 2p^{2}$ for $q=2$, we obtain the following bound
on exponential moments (recall that $\mathbf{E}Z=0$):

$\displaystyle\begin{aligned} \mathbf{E}\mathrm{e}^{tZ}&\leqslant
1+t^{2}p^{2}+\sum_{r\geqslant
2}p^{r}\sum_{q\geqslant\max\\{3,r\\}}\frac{(2tr)^{q}}{q!}\\\
&=1+t^{2}p^{2}+\sum_{r\geqslant
2}p^{r}\mathrm{e}^{2tr}\mathbf{P}\left\\{\mathsf{Poiss}(2tr)\geqslant\max\\{3,r\\}\right\\}\\\
&=1+t^{2}p^{2}+p^{2}(\mathrm{e}^{4t}-8t^{2}-4t-1)+\sum_{r\geqslant
3}p^{r}\mathrm{e}^{2tr}\mathbf{P}\left\\{\mathsf{Poiss}(2tr)\geqslant
r\right\\}\end{aligned}.$ (17)

Using the known bound $\mathbf{P}\left\\{\mathsf{Poiss}(2tr)\geqslant
r\right\\}\leqslant\mathrm{e}^{-2tr}(2\mathrm{e}t)^{r}$ for the Poisson
distribution tails (it is obtained from the moment generating function, see
[10] or the next section for an implicit derivation) for $t<\frac{1}{2}$ and
$\mathbf{P}\left\\{\mathsf{Poiss}(2tr)\geqslant r\right\\}\leqslant 1$ for
$t\geqslant\frac{1}{2}$ we obtain the following bound

$\displaystyle\mathbf{E}\mathrm{e}^{tZ}\leqslant
1+t^{2}p^{2}+p^{2}(\mathrm{e}^{4t}-8t^{2}-4t-1)+\begin{cases}\frac{(2\mathrm{e}pt)^{3}}{1-2\mathrm{e}pt}&\quad
0<t<\frac{1}{2}\\\
\frac{p^{3}\mathrm{e}^{6t}}{1-p\mathrm{e}^{2t}}&\quad\frac{1}{2}\leqslant
t<\frac{\log(1/p)}{2}\end{cases}.$ (18)

We transform the bound into the form

$\displaystyle\mathbf{E}\mathrm{e}^{tZ}\leqslant
1+t^{2}p^{2}+p^{2}\cdot\underbrace{\begin{cases}\mathrm{e}^{4t}-8t^{2}-4t-1+{\frac{8\mathrm{e}^{3}pt^{3}}{1-2\mathrm{e}pt}}&\quad
0<t<\frac{1}{2}\\\
\mathrm{e}^{4t}-8t^{2}-4t-1+\frac{p\mathrm{e}^{6t}}{1-p\mathrm{e}^{2t}}&\quad\frac{1}{2}\leqslant
t<\frac{\log(1/p)}{2}\end{cases}}_{\psi(t,p)},$ (19)

and observe that the following numerical inequality holds

$\displaystyle\psi(t,p)\leqslant\frac{\mathrm{e}^{Kt}-\frac{K^{2}t^{2}}{2}-Kt-1}{K^{2}/2},\quad
0<t\leqslant\frac{\log(1/2p)}{2},$ (20)

for some sufficiently large constant $K$, which gives us the bound

$\displaystyle\mathbf{E}\mathrm{e}^{tZ}\leqslant
1+2p^{2}\cdot\frac{\mathrm{e}^{Kt}-Kt-1}{K^{2}},\quad
0<t\leqslant\frac{\log(1/2p)}{2}.$ (21)

This specific function is chosen as the upper bound because it appears in the
exponential moments of Poisson random variables, making computations
tracktable. relation to Poisson - explain here or in intro?

We know prove that Equation 20 holds with $K=50$; to this end we use the
series expansion and compare the coefficients. Specificailly, we consider the
two cases:

  1. 1.

For $0<t<\frac{1}{2}$ the LHS is bounded by $6t^{3}+\sum_{r\geqslant
3}\frac{4^{r}t^{r}}{r!}$ (for $p\leqslant\frac{1}{30},t\leqslant\frac{1}{2}$
we have ${\frac{8\mathrm{e}^{3}pt^{3}}{1-2\mathrm{e}pt}}\leqslant 6t^{3}$)
while the RHS equals $\sum_{r\geqslant 3}\frac{2K^{r-2}t^{r}}{r!}$; we find
that the coefficients are accordingly dominated when $4^{r}\leqslant 2K^{r-2}$
for $r\geqslant 4$ and when $\frac{64}{3!}+6\leqslant\frac{2K}{3!}$. These
conditions are satisfied for $K=50$.

  2. 2.

For $\frac{1}{2}\leqslant t\leqslant\frac{\log(1/2p)}{2}$ the LHS is bounded
by $1+4t+8t^{2}+2\sum_{r\geqslant 3}\frac{4^{r}t^{r}}{r!}$ while the RHS
equals $\sum_{r\geqslant 3}\frac{2K^{r-2}t^{r}}{r!}$. It suffices when
$4^{r}<2K^{r-2}$ for $r\geqslant 4$ and
$1+4t+8t^{2}+\frac{2t^{3}}{3!}\leqslant\frac{2Kt^{3}}{3!}$. These conditions
are satisfied when $K=50$ and $\frac{1}{2}\leqslant t$.

###  3.4 Aggregating Bounds

Applying the last bound to $Z_{i}\sim^{iid}Z$ and using the inequality
$\log(1+u)\leqslant u$, we get

$\displaystyle\log\mathbf{E}\mathrm{e}^{t\cdot(Z_{1}+\cdots+Z_{m})}\leqslant
2mp^{2}\cdot\frac{\mathrm{e}^{Kt}-Kt-1}{K^{2}},\quad
0<t<\frac{\log(1/2p)}{2}.$ (22)

Using the Cramer-Chernoff inequality with $t^{*}=\frac{\log(1+Ku/2mp^{2})}{K}$
we obtain (note: calculations may be facilitated with symbolic algebra
software (see Appendix A))

$\displaystyle\mathbf{P}\left\\{Z_{1}+\cdots+Z_{m}\geqslant
u\right\\}\leqslant\mathrm{e}^{-\frac{u^{2}}{4mp^{2}}\cdot
h\left(\frac{Ku}{2mp^{2}}\right)},\quad
h(u)\triangleq\frac{(1+u)\log(1+u)-u}{u^{2}/2},$ (23)

for all $u$ satisfying the condition

$\displaystyle\ \frac{\log(1+Ku/2mp^{2})}{K}\leqslant\frac{\log(1/2p)}{2}.$
(24)

For our case we use $u=s\epsilon$, then the condition becomes
$\frac{\log(1+K\epsilon/2p)}{K}\leqslant\frac{\log(1/2p)}{2}$, and is
satisfied when $\epsilon<p\log(1/2p)$ (we use $\log(1+u)\leqslant u$ with
$u=K\epsilon/2p$). We then obtain

$\displaystyle\mathbf{P}\left\\{\frac{Z_{1}+\cdots+Z_{m}}{s}\geqslant\epsilon\right\\}\leqslant\mathrm{e}^{-\frac{m\epsilon^{2}}{4}\cdot
h\left(\frac{K\epsilon}{2p}\right)}.$ (25)

Due to Equation 9, this discussion implies

$\displaystyle\max\\{\mathbf{P}\left\\{x^{T}Bx\geqslant\epsilon\right\\},\mathbf{P}\left\\{x^{T}Bx\leqslant-\epsilon\right\\}\\}\leqslant\mathrm{e}^{-\frac{m\epsilon^{2}}{4}\cdot
h\left(\frac{K\epsilon}{2p}\right)},$ (26)

which completes the proof.

## References

  * [1] Vladimir Braverman, Rafail Ostrovsky, and Yuval Rabani.  Rademacher chaos, random eulerian graphs and the sparse Johnson-Lindenstrauss transform.  arXiv preprint arXiv:1011.2590, 2010.
  * [2] Michael Burr, Shuhong Gao, and Fiona Knoll.  Optimal bounds for johnson-lindenstrauss transformations.  The Journal of Machine Learning Research, 19(1):2920–2941, 2018\.
  * [3] Michael B Cohen.  Nearly tight oblivious subspace embeddings by trace inequalities.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 278–287. SIAM, 2016.
  * [4] Michael B Cohen, TS Jayram, and Jelani Nelson.  Simple analyses of the sparse Johnson-Lindenstrauss transform.  In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [5] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós.  A sparse Johnson-Lindenstrauss transform.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 341–350, 2010.
  * [6] Kumar Joag-Dev and Frank Proschan.  Negative association of random variables with applications.  The Annals of Statistics, pages 286–295, 1983.
  * [7] Daniel Kane, Raghu Meka, and Jelani Nelson.  Almost optimal explicit johnson-lindenstrauss families.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 628–639. Springer, 2011.
  * [8] Daniel M. Kane and Jelani Nelson.  A derandomized sparse Johnson-Lindenstrauss transform.  Electron. Colloquium Comput. Complex., 17:98, 2010.  URL: http://dblp.uni-trier.de/db/journals/eccc/eccc17.html#KaneN10.
  * [9] Daniel M Kane and Jelani Nelson.  Sparser Johnson-Lindenstrauss transforms.  In Society for Industrial and Applied Mathematics and Association for Computing Machinery. Proceeding of the ACM-SIAM Symposium on Discrete Algorithms, page 1195. Society for Industrial and Applied Mathematics, 2012.
  * [10] David Pollard.  Mini empirical.  Manuscript. http://www. stat. yale. edu/pollard/Books/Mini, 2015\.

##  Appendix A Chernoff Bounds for Sub-Poisson Tails

Suppose that
$\mathbf{E}[\mathbf{e}^{tX}]\leqslant\mathrm{e}^{v^{2}\cdot\frac{\mathrm{e}^{Kt}-Kt-1}{K^{2}}}$,
we then show that the Chernoff inequality gives
$\mathbf{P}\\{X>\epsilon\\}\leqslant\mathrm{e}^{-\frac{\epsilon^{2}}{2v}\cdot
2\left(\frac{K\epsilon}{v}\right)^{-2}\left(\left(1+\frac{K\epsilon}{v}\right)\log{\left(1+\frac{K\epsilon}{v}\right)}-\frac{K\epsilon}{v}\right)}$.
See the code for LABEL:alg:chernoff_sub_poiss.

Listing 1: Chernoff Inequality

⬇

import sympy as sm

sm.init_printing(use_latex=True)

v,K,t,eps,u = sm.symbols(’v K t epsilon u’)

log_MGF = v*(sm.exp(K*t)-K*t-1)/K**2

t_best = sm.solve((log_MGF-t*eps).diff(t),t)[0]

logp = (log_MGF-t*eps).subs({t:t_best}).factor()

out = logp.subs({K*eps:u*v}).factor().collect(sm.log(u+1))

bennet = ((1+u)*sm.log(1+u)-u)/(u**2/sm.Rational(2,1))

gauss = (out/bennet)

gauss = gauss.subs({u:K*eps/v}).simplify()

bennet = bennet.subs({u:sm.UnevaluatedExpr(K*eps/v)})

gauss*bennet


###### Abstract.

In this article we provide a generalization of the Brocard circle and the
Brocard triangles. The generalization arises from considering the Miquel
points of two inscribed triangles having a common circumcircle. We also state
some known properties which still hold in the generalized setting.

A Generalization of the Brocard Circles and the Brocard Triangles

A GENERALIZATION OF THE BROCARD CIRCLE

SUDHARSHAN K V

Abstract. In this article we provide a generalization of the Brocard circle
and the Brocard triangles. The generalization arises from considering the
Miquel points of two inscribed triangles having a common circumcircle. We also
present various properties of the Brocard triangles, which lead to a
generalization of the Steiner and Tarry points.

##  1\. Introduction

The Brocard points, named after French Geometer Henri Brocard, have been a
subject of significant interest and study in the field of Euclidean geometry.
They have been studied extensively (see [3], [2]). In this section, we recall
the definitions of the Brocard points, the Brocard circle, and the Brocard
triangles. We shall also state some known properties which are retained in the
generalization developed in this paper.

Throughout the paper, let $ABC$ be an anticlockwise oriented triangle.

######  Definition 1.1 (Brocard Points).

The first and second Brocard Points $\Omega,\Omega^{\prime}$ of $\triangle
ABC$ are interior points satisfying the angle conditions:

$\angle\Omega AB=\angle\Omega BC=\angle\Omega
CA~{}\text{and}~{}\angle\Omega^{\prime}AC=\angle\Omega^{\prime}BA=\angle\Omega^{\prime}CB.$

We introduce circles $\omega_{A},\omega_{B},\omega_{C}$, and
$\omega_{A}^{\prime},\omega_{B}^{\prime},\omega_{C}^{\prime}$ as follows:

  * •

Circle $\omega_{A}$ passes through $A$ and is tangent to side $BC$ at $B$.

  * •

Circle $\omega_{B}$ passes through $B$ and is tangent to side $CA$ at $C$.

  * •

Circle $\omega_{C}$ passes through $C$ and is tangent to side $AB$ at $A$.

Similarly, in a cyclic fashion:

  * •

Circle $\omega_{A}^{\prime}$ passes through $A$ and is tangent to side $BC$ at
$C$.

  * •

Circle $\omega_{B}^{\prime}$ passes through $B$ and is tangent to side $CA$ at
$A$.

  * •

Circle $\omega_{C}^{\prime}$ passes through $C$ and is tangent to side $AB$ at
$B$.

————————————–

Keywords and phrases: Brocard Points, Brocard Triangle, Brocard Circle

(2020)Mathematics Subject Classification: 51P99, 60A99

It can be observed that the first Brocard point $\Omega$ is the common point
of intersection of circles $\omega_{A},\omega_{B},\omega_{C}$. On the other
hand, the second Brocard point $\Omega^{\prime}$ is the common point of
intersection of circles
$\omega_{A}^{\prime},\omega_{B}^{\prime},\omega_{C}^{\prime}$. Furthermore, it
is well-established that $\Omega$ and $\Omega^{\prime}$ are isogonal
conjugates in the reference triangle $\triangle ABC$.

######  Definition 1.2 (Miquel Points).

Let $D,E,F$ be points on the sidelines $BC,CA,AB$ respectively. The Miquel
point of $\triangle DEF$ in $\triangle ABC$ is the common point of the
circumcircles of $\triangle AEF$, $\triangle BFD$, and $\triangle CDE$.
Let $A,B,C,D$ be four general points, and let $P=AB\cap CD$, $Q=AD\cap BC$.
The Miquel point of quadrangle $ABCD$ is the common point of the circumcircles
of $\triangle PAD$, $\triangle PBC$, $\triangle QAB$ and $\triangle QCD$.

The two Brocard points of $\triangle ABC$ are therefore the Miquel points of
$\triangle BCA$ and $\triangle CAB$ in $\triangle ABC$. This view of the
Brocard points leads to a generalization (Section 2.2), where we study Miquel
points of two inscribed triangles that share a circumcircle.

######  Definition 1.3 (Brocard Triangles).

(See [6], [7], and [8]) The vertices of the first Brocard triangle are defined
as $A_{1}=\Omega B\cap\Omega^{\prime}C$, $B_{1}=\Omega C\cap\Omega^{\prime}A$,
and $C_{1}=\Omega A\cap\Omega^{\prime}B$.
On the other hand, the second Brocard triangle has its vertices denoted as
$A_{2}=\omega_{A}\cap\omega_{A}^{\prime},B_{2}=\omega_{B}\cap\omega_{B}^{\prime}$,
and $C_{2}=\omega_{C}\cap\omega_{C}^{\prime}$, where these intersection points
are distinct from $A$, $B$, and $C$.

Figure 1. Brocard Points and associated Objects

It is known that $\triangle A_{1}B_{1}C_{1}$ and $\triangle A_{2}B_{2}C_{2}$
have the same circumcircle. This circle is called the Brocard Circle, and we
know that the circumcenter $O$ and symmedian point $K$ of $\triangle ABC$ are
diametrically opposite points in this circle.
The construction we present to generalize the Brocard points extends to a
generalization of the Brocard circle and the Brocard triangles, as detailed in
Section 3.1.

##  2\. A Generalization of the Brocard Points

Firstly, we present several well-known and useful Lemmas.

###  2.1. Preliminary Lemmas

######  Lemma 2.1.

Let $M$ be the Miquel point of $\triangle DEF$ in $\triangle ABC$. Then,
$\triangle DEF$ is the image of the pedal triangle of $M$ in $\triangle ABC$
under a spiral similarity centered at $M$.

Proof. Throughout the paper, we represent the directed measure (modulo $\pi$)
of an angle $\theta$ as $\measuredangle\theta$.

Let $\triangle D^{\prime}E^{\prime}F^{\prime}$ be the pedal triangle of point
$M$ with respect to $\triangle ABC$. Since $M$ is the Miquel point, we observe
that $\measuredangle MDB=\measuredangle MFA=\measuredangle MEC$. Additionally,
$\measuredangle MD^{\prime}B=\measuredangle MF^{\prime}A=\measuredangle
ME^{\prime}C=90^{\circ}$. Rewriting the angle relations, we find that
$\measuredangle MDD^{\prime}=\measuredangle MEE^{\prime}=\measuredangle
MFF^{\prime}$ and $\measuredangle MD^{\prime}D=\measuredangle
ME^{\prime}E=\measuredangle MF^{\prime}F=90^{\circ}$.

As a consequence of these angle relationships, we establish that $\triangle
MDD^{\prime}\stackrel{{\scriptstyle+}}{{\sim}}\triangle
MEE^{\prime}\stackrel{{\scriptstyle+}}{{\sim}}\triangle MFF^{\prime}$. This
similarity leads to the existence of a spiral similarity $\Psi_{M}$ centered
at point $M$, which maps $\triangle D^{\prime}E^{\prime}F^{\prime}$ to
$\triangle DEF$.

######  Lemma 2.2.

Let $M$ be the Miquel point of $\square ABCD$, where $A,B,C,D$ lie on a circle
$\odot(O,r)$. Let $P=AB\cap CD$, $Q=AD\cap BC$. Then $OM\perp PQ$ and $M\in
PQ$.

Figure 2. Miquel Point of a Cyclic Quadrangle

Proof. Consider the points $R=AC\cap BD$ and $R^{*}$, which is the inverse of
$R$ in the circumcircle of quadrilateral $ABCD$ which we denote by
$\odot(ABCD)$. We shall show that $R^{*}=M$.

Let $\overline{\chi}$ represent the directed length of a segment $\chi$. It is
evident that
$\overline{RR^{*}}\cdot\overline{RO}=RO^{2}-r^{2}=\overline{RA}\cdot\overline{RC}$,
which implies that $R^{*},O,A,C$ are concyclic. Similarly, $R^{*},O,B,D$ are
concyclic. Through some angle-chasing, we find that $\measuredangle
AR^{*}B=\measuredangle AR^{*}O+\measuredangle OR^{*}B=\measuredangle
ACO+\measuredangle ODB=90^{\circ}-\measuredangle CDA+90^{\circ}-\measuredangle
BCD=\measuredangle QCD+\measuredangle CDQ=\measuredangle AQB$, which leads to
$\measuredangle AR^{*}B=\measuredangle AQB$. It follows that $\square
AR^{*}QB$ is cyclic. Similarly, $\square AR^{*}PD$, $\square BR^{*}CP$, and
$\square CR^{*}DQ$ are cyclic, which gives us $R^{*}=M$.

Finally, applying Brokard’s theorem on $\square ABCD$ shows that $OM$ is an
altitude of $\triangle POQ$.

######  Lemma 2.3.

The angle between Simson lines $\ell_{M},\ell_{N}$ of two points $M,N$ in
$\odot(ABC)$ is half the measure of arc ${MN}$. More precisely,
$\measuredangle(\ell_{M},\ell_{N})=\measuredangle MAN$.

The proof of the final lemma is omitted. It can be found in any standard text,
such as [1].

###  2.2. Generalized Brocard Points

Let a circle $\Gamma$ centered at $O$ intersect sides $BC,CA$, and $AB$ of a
$\triangle ABC$ (oriented anticlockwise) at $\\{A_{1},A_{2}\\}$,
$\\{B_{1},B_{2}\\}$, and $\\{C_{1},C_{2}\\}$. Let $P$ and $Q$ be the Miquel
Points of $\triangle A_{1}B_{1}C_{1}$, $\triangle A_{2}B_{2}C_{2}$ in
$\triangle ABC$ respectively.

######  Theorem 2.1 (see [4]).

The points $P$ and $Q$ are isogonal conjugates in $\triangle ABC$, and we have
an equality of angles $\measuredangle PA_{1}A_{2}=\measuredangle PB_{1}B_{2}$
$=\measuredangle PC_{1}C_{2}$ $=-\measuredangle QA_{2}A_{1}$ $=-\measuredangle
QB_{2}B_{1}$ $=\measuredangle QC_{2}C_{1}$.

Figure 3. Generalized Brocard Points

Proof. We provide a combined proof for both parts, inspired by Minjae Kwon’s
proof in [5]. Let us redefine points $Q$, $A_{2}$, $B_{2}$, and $C_{2}$ from
the given point $P$.

First, we redefine $Q$ as the isogonal conjugate of $P$ in $\triangle ABC$.
Next, we redefine points $A_{2}$, $B_{2}$, and $C_{2}$ as new points on $BC$,
$CA$, and $AB$, respectively, such that the following conditions hold:

$\displaystyle\measuredangle PA_{1}A_{2}$ $\displaystyle=-\measuredangle
QA_{2}A_{1},$ $\displaystyle\measuredangle PB_{1}B_{2}$
$\displaystyle=-\measuredangle QB_{2}B_{1},$ $\displaystyle\measuredangle
PC_{1}C_{2}$ $\displaystyle=-\measuredangle QC_{2}C_{1}.$

Since $P$ is the Miquel point of $\triangle A_{1}B_{1}C_{1}$, it follows that
$-\measuredangle PA_{1}C=-\measuredangle PB_{1}A=-\measuredangle
PC_{1}B=\measuredangle QA_{2}C=\measuredangle QB_{2}A=\measuredangle QC_{2}B$.
This equality allows us to deduce that $Q$ is the Miquel Point of $\triangle
A_{2}B_{2}C_{2}$.

We now proceed to show that $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$, $C_{1}$, and
$C_{2}$ are concyclic. From the new definitions, we have:

$\displaystyle\measuredangle CA_{1}P$ $\displaystyle=-\measuredangle CB_{2}Q,$
$\displaystyle\measuredangle PCA_{1}$ $\displaystyle=-\measuredangle QCB_{2}.$

Thus, we can observe that $\triangle
CPA_{1}\stackrel{{\scriptstyle-}}{{\sim}}\triangle CQB_{2}$. Analogously, we
have $\triangle CQA_{2}\stackrel{{\scriptstyle-}}{{\sim}}\triangle CPB_{1}$,
leading to the relation

$\frac{CA_{1}}{CB_{2}}=\frac{CB_{1}}{CA_{2}}=\frac{CP}{CQ}.$

Consequently, $CA_{1}\cdot CA_{2}=CB_{1}\cdot CB_{2},$ which implies that the
quadrangle $\square A_{1}A_{2}B_{1}B_{2}$ is cyclic. Similarly, one shows that
the quadrangles $\square B_{1}B_{2}C_{1}C_{2}$ and $\square
A_{1}A_{2}C_{1}C_{2}$ are also cyclic.

If the circles $\odot(A_{1}A_{2}B_{1}B_{2})$, $\odot(A_{1}A_{2}C_{1}C_{2})$,
and $\odot(B_{1}B_{2}C_{1}C_{2})$ were distinct, their pairwise radical axes
would meet at a point, which would lead to a contradiction. Hence, the three
circles coincide, confirming that $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$, $C_{1}$,
and $C_{2}$ lie on a single circle. These new definitions of $A_{2}$, $B_{2}$,
and $C_{2}$ agree with the original definitions, thereby completing the proof.

######  Remark 2.1.

Consider the spiral similarities $\Psi_{P},\Psi_{Q}$ centered at $P,Q$ taking
their pedal triangles to $\triangle A_{1}B_{1}C_{1}$ and $\triangle
A_{2}B_{2}C_{2}$ respectively. Using Theorem 2.1, we observe that the
(directed) angles of rotation $\theta_{P},\theta_{Q}$ associated with
$\Psi_{P},\Psi_{Q}$ bear the relation

$\theta_{P}+\theta_{Q}=0.$

##  3\. A Generalization of the Brocard Circle and Triangles

We now build on the configuration from Section 2.2, by defining the three
points

$T_{A}=PA_{1}\cap QA_{2},T_{B}=PB_{1}\cap QB_{2},\text{ and }T_{C}=PC_{1}\cap
QC_{2}.$

We also introduce three other points

$A^{\prime}=\odot(AB_{1}C_{1})\cap\odot(AB_{2}C_{2}),$
$B^{\prime}=\odot(BC_{1}A_{1})\cap\odot(BC_{2}A_{2}),$

and

$C^{\prime}=\odot(CA_{1}B_{1})\cap(CA_{2}B_{2}).$

######  Proposition 3.1.

The lines $AA^{\prime},BB^{\prime},CC^{\prime}$ are concurrent.

Proof. The points $A_{0}=B_{1}C_{2}\cap C_{1}B_{2}$, $B_{0}=A_{1}C_{2}\cap
C_{1}A_{2}$, and $C_{0}=A_{1}B_{2}\cap B_{1}A_{2}$ lie on the same line, due
to Pascal’s theorem applied to the hexagon $A_{1}B_{1}C_{1}A_{2}B_{2}C_{2}$.

Now, let $R$ be the pole of the line $A_{0}B_{0}C_{0}$ with respect to the
circle $\Gamma$. By applying the Radical Axis theorem to $\odot(AB_{1}C_{1})$,
$\odot(AB_{2}C_{2})$, and $\Gamma$, we find that lines $B_{1}C_{1}$,
$B_{2}C_{2}$, and $AA^{\prime}$ are concurrent. Moreover, from Brokard’s
theorem applied to the quadrilateral $B_{1}C_{1}B_{2}C_{2}$, we deduce that
$AA^{\prime}$ is the polar of point $A_{0}$ with respect to $\Gamma$. As
$AA^{\prime}$ passes through $R$ due to La Hire’s theorem, similarly,
$BB^{\prime}$ and $CC^{\prime}$ pass through $R$. Thus, we conclude that the
lines $AA^{\prime}$, $BB^{\prime}$, and $CC^{\prime}$ are concurrent at point
$R$.

###  3.1. Generalization of the Brocard Circle

We present the generalization of the Brocard circle in the following theorem.

######  Theorem 3.1.

The points $P,Q,O,R,A^{\prime},B^{\prime},C^{\prime},T_{A},T_{B},T_{C}$ lie on
a circle.

Figure 4. Generalized Brocard Circle

Proof. Observe that $A^{\prime}$ is the Miquel point of $\square
C_{1}C_{2}B_{2}B_{1}$ since
$A^{\prime}=\odot(AB_{1}C_{1})\cap\odot(AB_{2}C_{2})$. By applying Lemma 2.2,
we deduce that $\angle OA^{\prime}A=90^{\circ}$. Considering that
$AA^{\prime}$ passes through $R$, we can infer that $\angle
OA^{\prime}R=90^{\circ}$. Similarly, $\angle OB^{\prime}R=\angle
OC^{\prime}R=90^{\circ}$, from which we can conclude that
$A^{\prime},B^{\prime},C^{\prime}$ lie on the circle with diameter $OR$.

Upon chasing angles, we find $\measuredangle PA^{\prime}Q=\measuredangle
PA^{\prime}C-\measuredangle QA^{\prime}C=\measuredangle PA_{1}C-\measuredangle
QA_{2}C$. Employing Theorem 2.1, we have $\measuredangle
PA_{1}C=-\measuredangle QA_{2}C$, which yields $\measuredangle
PA^{\prime}Q=\theta_{Q}-\theta_{P}$ (also equal to $2\theta_{Q}$). As this
expression is symmetric in $A,B,C$, it follows that $\measuredangle
PA^{\prime}Q=\measuredangle PB^{\prime}Q=\measuredangle PC^{\prime}Q$. Thus,
$P$ and $Q$ lie on the circle $\odot(A^{\prime}B^{\prime}C^{\prime})$.

Furthermore, we observe that $\measuredangle PT_{A}Q=\measuredangle
PA_{1}A_{2}+\measuredangle A_{1}A_{2}Q=\theta_{Q}-\theta_{P}=\measuredangle
PA^{\prime}Q$. Consequently, $T_{A}$ lies on
$\odot(A^{\prime}B^{\prime}C^{\prime})$. Similarly, we can deduce that $T_{B}$
and $T_{C}$ also lie on $\odot(A^{\prime}B^{\prime}C^{\prime})$. Consequently,
the points $P,Q,O,R,A^{\prime},B^{\prime},C^{\prime},T_{A},T_{B},T_{C}$ are
all concyclic.

######  Corollary 3.1.

The points $P$ and $Q$ are equidistant from $R$.

Proof. We can observe from Theorem 2.1 that $\triangle T_{A}A_{1}A_{2}$ is
isosceles, with $T_{A}A_{1}=T_{A}A_{2}$. Since $OT_{A}$ is the perpendicular
bisector of $A_{1}A_{2}$, $OT_{A}$ is the angle bisector of $\angle
A_{1}T_{A}A_{2}$. So, $OT_{A}$ bisects $\angle PT_{A}Q$. Also, $O$ lies on the
circumcircle of $\triangle T_{A}PQ$. Therefore, $OP=OQ$. Since $OR$ is a
diameter of this circle, the result follows.

######  Remark 3.1.

Minjae Kwon (in [5]) shows a more general result: For $\triangle DEF$ and
$\triangle XYZ$ inscribed in $\triangle ABC$, where $\\{D,X\\},\\{E,Y\\}$, and
$\\{F,Z\\}$ are points on $BC,CA$, and $AB$ respectively.) Suppose that the
perpendicular bisectors of $DX,EY,CZ$ concur at a point, $T$. If $O_{1},O_{2}$
are the Miquel points of $\triangle DEF,\triangle XYZ$, then $TO_{1}=TO_{2}$.

###  3.2. Revisiting the Brocard Points, Circle and Triangles

As discussed in Section 1, a special case arises when $A_{1}=B$, $B_{1}=C$,
$C_{1}=A$, $A_{2}=C$, $B_{2}=A$, $C_{2}=B$. In this scenario, the points $P$
and $Q$ coincide with the first and second Brocard points, $\Omega$ and
$\Omega^{\prime}$, respectively, of $\triangle ABC$. The circle $\Gamma$
transforms into the circumcircle of $\triangle ABC$, and $O$ becomes the
circumcenter. Additionally, the points $A_{0}$, $B_{0}$, and $C_{0}$
correspond to the intersections of the tangents to the circumcircle at the
vertices of $\triangle ABC$ with the opposite sides. Then, the symmedian point
$K$ of $\triangle ABC$ coincides with the pole of the line $A_{0}B_{0}C_{0}$
with respect to the circumcircle, thus making $R=K$.

Furthermore, we observe that the triangles $\triangle T_{A}T_{B}T_{C}$ and
$\triangle A^{\prime}B^{\prime}C^{\prime}$ become the first and second Brocard
triangles, respectively. One can now see the proofs of several results from
Section 1. Indeed, applying Theorem 3.1 demonstrates that the circle with
diameter $OK$ passes through $\Omega$ and $\Omega^{\prime}$ and also through
the vertices of the first and second Brocard Triangles. Moreover, Corollary
3.1 reveals that $OK$ is the perpendicular bisector of
$\Omega\Omega^{\prime}$.

##  4\. Properties of the Generalized Brocard Triangles

Various properties of the Brocard triangles carry over to the generalization.
We present a few in this section.

######  Proposition 4.1.

We have a similarity $\triangle
T_{A}T_{B}T_{C}\stackrel{{\scriptstyle-}}{{\sim}}\triangle ABC$ of the
(generalized) first Brocard triangle with the reference triangle.

Proof. Observe that $OT_{A}\perp BC$ since $OT_{A}$ is the perpendicular
bisector of $A_{1}A_{2}$. Similarly, $OT_{B}\perp AC$, indicating that
$\measuredangle T_{A}OT_{B}=\measuredangle BCA$. By utilizing Theorem 3.1, we
find that $\measuredangle T_{A}OT_{B}=\measuredangle T_{A}T_{C}T_{B}$,
resulting in $\measuredangle T_{A}T_{C}T_{B}=-\measuredangle ACB$.
Analogously, we obtain similar relationships, leading to the similarity
$\triangle T_{A}T_{B}T_{C}\stackrel{{\scriptstyle-}}{{\sim}}\triangle ABC$.

######  Proposition 4.2 (Generalized Steiner Point).

The parallels from $A,B,C$ to $T_{B}T_{C}$, $T_{C}T_{A}$, $T_{A}T_{B}$ are
concurrent on $\odot(ABC)$.

Proof. Consider the parallels drawn from points $A$ and $B$ to the lines
$T_{B}T_{C}$ and $T_{C}T_{A}$, respectively, which intersect at a point
$S_{t}$. We can observe that $\measuredangle AS_{t}B=\measuredangle
T_{B}T_{C}T_{A}=\measuredangle ACB$, where the last equality follows from
Proposition 4.1. Consequently, $S_{t}$ lies on the circumcircle of $\triangle
ABC$.

Further, we have $\measuredangle AS_{t}C=\measuredangle ABC=\measuredangle
T_{C}T_{B}T_{A}$. As $AS_{t}\parallel T_{B}T_{C}$, it follows that
$CS_{t}\parallel T_{A}T_{B}$. This leads us to the conclusion that the
parallels drawn from points $A$, $B$, and $C$ to the lines $T_{B}T_{C}$,
$T_{C}T_{A}$, and $T_{A}T_{B}$, respectively, are concurrent at point $S_{t}$,
which lies on $\odot(ABC)$.

######  Corollary 4.1 (Generalized Tarry Point).

The perpendiculars from $A,B,C$ to $T_{B}T_{C}$, $T_{C}T_{A}$, $T_{A}T_{B}$
are concurrent on the antipode $T_{a}$ of $S_{t}$ in $\odot(ABC)$.

######  Proposition 4.3.

We have a similarity of polygons

$\triangle ABC\cup S_{t}\cup T_{a}\stackrel{{\scriptstyle-}}{{\sim}}\triangle
T_{A}T_{B}T_{C}\cup R\cup O.$

Proof. In the proof of Theorem 3.1, we established that $OR$ is the diameter
of $\odot(T_{A}T_{B}T_{C})$ and $OT_{A}\perp BC$, implying $RT_{A}\parallel
BC$. Additionally, as $AS_{t}\parallel T_{B}T_{C}$, we find that
$\measuredangle(\overline{BC},\overline{AS_{t}})=-\measuredangle(\overline{T_{B}T_{C}},\overline{T_{A}R})$.
Then, utilizing the similarity in Proposition 4.1, we arrive at the similarity

$\triangle ABC\cup S_{t}\stackrel{{\scriptstyle-}}{{\sim}}\triangle
T_{A}T_{B}T_{C}\cup R.$

Further, the pairs ${T_{a},S_{t}}$ and ${O,R}$ are antipodal points in
$\odot(ABC)$ and $\odot(T_{A}T_{B}T_{C})$, respectively. Hence, one obtains
the similarity

$\triangle ABC\cup S_{t}\cup T_{a}\stackrel{{\scriptstyle-}}{{\sim}}\triangle
T_{A}T_{B}T_{C}\cup R\cup O.$

Figure 5. Generalized Brocard Triangles and their properties

######  Proposition 4.4.

The triangles $T_{A}T_{B}T_{C}$ and $A^{\prime}B^{\prime}C^{\prime}$ are
perspective.

Proof. Let $R^{*}$ denote the isogonal conjugate of $R$ in $\triangle ABC$.
Introduce a point $S$ such that $\triangle T_{A}T_{B}T_{C}\cup
S\stackrel{{\scriptstyle-}}{{\sim}}\triangle ABC\cup R^{*}$. From the proof of
Theorem 3.1, we know that $OB^{\prime}\perp BR$ and $OT_{A}\perp BC$.
Consequently, we obtain $\measuredangle T_{A}OB^{\prime}=-\measuredangle RBC$.
As $\measuredangle T_{A}T_{B}B^{\prime}=\measuredangle T_{A}OB^{\prime}$ and
$\measuredangle R^{*}BA=-\measuredangle RBC$, it follows that $\measuredangle
R^{*}BA=\measuredangle T_{A}T_{B}B^{\prime}$.

By definition of point $S$, we have $-\measuredangle ABR^{*}=\measuredangle
T_{A}T_{B}S$. Thus, we find that $\measuredangle T_{A}T_{B}S=\measuredangle
T_{A}T_{B}B^{\prime}$, implying that $T_{B}B^{\prime}$ passes through $S$.
Similarly, we can establish that $T_{A}A^{\prime}$ and $T_{C}C^{\prime}$ also
pass through $S$. Consequently, we can assert that $\triangle T_{A}T_{B}T_{C}$
and $\triangle A^{\prime}B^{\prime}C^{\prime}$ are perspective.

######  Proposition 4.5.

The Simson line of $S_{t}$ is parallel line $OR$.

Proof. Consider the Simson line $\ell_{S_{t}}$ of point $S_{t}$ with respect
to $\triangle ABC$. Let $\ell_{A}$ represent the $A$-altitude of $\triangle
ABC$, which is also the Simson line of point $A$ in $\triangle ABC$. Utilizing
Lemma 2.3, we find that

$\measuredangle(\ell_{S_{t}},\overline{BC})=\measuredangle(\ell_{S_{t}},\ell_{A})-90^{\circ}=\measuredangle
AS_{t}T_{a}=\measuredangle ORT_{A},$

where the last equality follows from Proposition 4.3. As proven in Proposition
4.3, we have $RT_{A}\parallel BC$. Consequently, we deduce that
$OR\parallel\ell_{S_{t}}$, showcasing the parallel relationship between the
line $OR$ and the Simson line $\ell_{S_{t}}$.

######  Corollary 4.2.

The Simson line of $T_{a}$ is perpendicular to $OR$.

######  Proposition 4.6.

Let $OR$ intersect $BC,CA$, and $AB$ at $X,Y,Z$. Let $O_{A},O_{B},$ and
$O_{C}$ be the circumcenters of $AYZ,BZX,$ and $CXY$. Triangles $ABC$ and
$O_{A}O_{B}O_{C}$ are perspective at $S_{t}$.

Proof. By using Proposition 4.5, one derives an angle equality:

$\displaystyle\measuredangle YZA$
$\displaystyle=\measuredangle(\ell_{S_{t}},AB)$
$\displaystyle=90^{\circ}-\measuredangle S_{t}BC$
$\displaystyle=90^{\circ}-\measuredangle S_{t}AC.$

We can now conclude that $AS_{t}$ passes through the circumcenter $O_{A}$ of
$\triangle AYZ$, after which it is clear that $ABC$ and $O_{A}O_{B}O_{C}$ are
perspective at point $S_{t}$.

## References

  * [1] Evan Chen.  Euclidean geometry in mathematical olympiads, volume 27.  American Mathematical Soc., 2021.
  * [2] Laura Guggenbuhl.  Henri brocard and the geometry of the triangle.  The Mathematical Gazette, 37(322):241–243, 1953.
  * [3] Ross Honsberger.  Episodes in nineteenth and twentieth century Euclidean geometry, volume 37.  Cambridge University Press, 1995.
  * [4] Mmukul Khedekar.  Beautiful geometry dealing with miquel points , isogonal conjugates.  https://artofproblemsolving.com/community/c6h2060398, 2020.
  * [5] Minjae Kwon.  lminsl.github.io/archives, 2020.
  * [6] Eric W Weisstein.  Brocard points.  https://mathworld. wolfram. com/, 2001.
  * [7] Eric W Weisstein.  First brocard triangle.  https://mathworld. wolfram. com/, 2003.
  * [8] Eric W Weisstein.  Second brocard triangle.  https://mathworld. wolfram. com/, 2003.

DEPARTMENT OF MATHEMATICS

INDIAN INSTITUTE OF SCIENCE

BANGALORE, INDIA

E-mail address<EMAIL_ADDRESS>