text:
Generates solutions with a gradient arborescence, with coefficients parameterized by an ES.

This emitter originates in Fontaine 2021. It leverages the gradient information of the objective and measure functions, generating new solutions around a solution point $$\boldsymbol{\theta}$$ using gradient arborescence, with coefficients drawn from a Gaussian distribution. Essentially, this means that the emitter samples coefficients $$\boldsymbol{c_i} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$$ and creates new solutions $$\boldsymbol{\theta'_i}$$ according to

$\boldsymbol{\theta'_i} \gets \boldsymbol{\theta} + c_{i,0} \boldsymbol{\nabla} f(\boldsymbol{\theta}) + \sum_{j=1}^k c_{i,j}\boldsymbol{\nabla}m_j(\boldsymbol{\theta})$

Where $$k$$ is the number of measures, and $$\boldsymbol{\nabla} f(\boldsymbol{\theta})$$ and $$\boldsymbol{\nabla} m_j(\boldsymbol{\theta})$$ are the objective and measure gradients of the solution point $$\boldsymbol{\theta}$$, respectively.

Based on how the solutions are ranked after being inserted into the archive (see ranker), the solution point $$\boldsymbol{\theta}$$ is updated with gradient ascent, and the coefficient distribution parameters $$\boldsymbol{\mu}$$ and $$\boldsymbol{\Sigma}$$ are updated with an ES (the default ES is CMA-ES).

Note

Unlike non-gradient emitters, GradientArborescenceEmitter requires calling ask_dqd() and tell_dqd() (in this order) before calling ask() and tell() to communicate the gradient information to the emitter.

Parameters
• archive (ribs.archives.ArchiveBase) – An archive to use when creating and inserting solutions. For instance, this can be ribs.archives.GridArchive.

• x0 (np.ndarray) – Initial solution.

• sigma0 (float) – Initial step size / standard deviation.

• lr (float) – Learning rate for the gradient optimizer.

• ranker (Callable or str) – The ranker is a RankerBase object that orders the solutions after they have been evaluated in the environment. This parameter may be a callable (e.g. a class or a lambda function) that takes in no parameters and returns an instance of RankerBase, or it may be a full or abbreviated ranker name as described in ribs.emitters.rankers.

• selection_rule ("mu" or "filter") – Method for selecting parents in CMA-ES. With “mu” selection, the first half of the solutions will be selected as parents, while in “filter”, any solutions that were added to the archive will be selected.

• restart_rule (int, "no_improvement", and "basic") – Method to use when checking for restarts. If given an integer, then the emitter will restart after this many iterations, where each iteration is a call to tell(). With “basic”, only the default CMA-ES convergence rules will be used, while with “no_improvement”, the emitter will restart when none of the proposed solutions were added to the archive.

• grad_opt (Callable or str) – Gradient optimizer to use for the gradient ascent step of the algorithm. The optimizer is a GradientOptBase object. This parameter may be a callable (e.g. a class or a lambda function) which takes in the theta0 and lr arguments, or it may be a full or abbreviated name as described in ribs.emitters.opt.

• grad_opt_kwargs (dict) – Additional arguments to pass to the gradient optimizer. See the gradient-based optimizers in ribs.emitters.opt for the arguments allowed by each optimizer. Note that we already pass in theta0 and lr.

• es (Callable or str) – The evolution strategy is an EvolutionStrategyBase object that is used to adapt the distribution from which new gradient coefficients are sampled. This parameter may be a callable (e.g. a class or a lambda function) that takes in the parameters of EvolutionStrategyBase along with kwargs provided by the es_kwargs argument, or it may be a full or abbreviated optimizer name as described in ribs.emitters.opt.

• es_kwargs (dict) – Additional arguments to pass to the evolution strategy optimizer. See the evolution-strategy-based optimizers in ribs.emitters.opt for the arguments allowed by each optimizer.

• normalize_grad (bool) – If true (default), then gradient infomation will be normalized. Otherwise, it will not be normalized.

• bounds – This argument may be used for providing solution space bounds in the future. This emitter does not currently support solution space bounds, as bounding solutions for DQD algorithms such as CMA-MEGA is an open problem. Hence, this argument must be set to None.

• batch_size (int) – Number of solutions to return in ask(). If not passed in, a batch size will be automatically calculated using the default CMA-ES rules. Note that batch_size does not include the number of solutions returned by ask_dqd(), but also note that ask_dqd() always returns one solution, i.e. the solution point.

• epsilon (float) – For numerical stability, we add a small epsilon when normalizing gradients in tell_dqd() – refer to the implementation here. Pass this parameter to configure that epsilon.

• seed (int) – Value to seed the random number generator. Set to None to avoid a fixed seed.

Raises
• ValueError – There is an error in x0 or initial_solutions.

• ValueErrorbounds is set even though it is not currently supported.

• ValueError – If restart_rule, selection_rule, or ranker is invalid.

Methods

 Samples new solutions from a gradient arborescence parameterized by a multivariate Gaussian distribution. Samples a new solution from the gradient optimizer. tell(solution_batch, objective_batch, ...[, ...]) Gives the emitter results from evaluating solutions. tell_dqd(solution_batch, objective_batch, ...) Gives the emitter results from evaluating the gradient of the solutions.

Attributes

 archive The archive which stores solutions generated by this emitter. batch_size Number of solutions to return in ask(). batch_size_dqd Number of solutions to return in ask_dqd(). epsilon The epsilon added for numerical stability when normalizing gradients in tell_dqd(). itrs The number of iterations for this emitter. lower_bounds (solution_dim,) array with lower bounds of solution space. restarts The number of restarts for this emitter. solution_dim The dimension of solutions produced by this emitter. upper_bounds (solution_dim,) array with upper bounds of solution space. x0 Initial solution for the optimizer.

Samples new solutions from a gradient arborescence parameterized by a multivariate Gaussian distribution.

The multivariate Gaussian is parameterized by the evolution strategy optimizer self._opt.

Note that this method returns batch_size - 1 solution as one solution is returned via ask_dqd.

Returns

(batch_size, solution_dim) array – a batch of new solutions to evaluate.

Samples a new solution from the gradient optimizer.

Call :meth:ask_dqd and :meth:tell_dqd (in this order) before calling :meth:ask and :meth:tell.

Returns

a new solution to evaluate.

tell(solution_batch, objective_batch, measures_batch, status_batch, value_batch, metadata_batch=None)[source]

Gives the emitter results from evaluating solutions.

The solutions are ranked based on the rank() function defined by self._ranker.

Parameters
• solution_batch (array-like) – (batch_size, solution_dim) array of solutions generated by this emitter’s ask() method.

• objective_batch (array-like) – 1d array containing the objective function value of each solution.

• measures_batch (array-like) – (batch_size, measure space dimension) array with the measure space coordinates of each solution.

• status_batch (array-like) – 1d array of ribs.archive.addstatus returned by a series of calls to archive’s add() method.

• value_batch (array-like) – 1d array of floats returned by a series of calls to archive’s add() method. for what these floats represent, refer to ribs.archives.add().

• metadata_batch (array-like) – 1d object array containing a metadata object for each solution.

tell_dqd(solution_batch, objective_batch, measures_batch, jacobian_batch, status_batch, value_batch, metadata_batch=None)[source]

Gives the emitter results from evaluating the gradient of the solutions.

Parameters
• solution_batch (array-like) – (batch_size, solution_dim) array of solutions generated by this emitter’s ask_dqd() method.

• objective_batch (array-like) – 1d array containing the objective function value of each solution.

• measures_batch (array-like) – (batch_size, measure space dimension) array with the measure space coordinates of each solution.

• jacobian_batch (array-like) – (batch_size, 1 + measure_dim, solution_dim) array consisting of Jacobian matrices of the solutions obtained from ask_dqd(). Each matrix should consist of the objective gradient of the solution followed by the measure gradients.

• status_batch (array-like) – 1d array of ribs.archive.addstatus returned by a series of calls to archive’s add() method.

• value_batch (array-like) – 1d array of floats returned by a series of calls to archive’s add() method. for what these floats represent, refer to ribs.archives.add().

• metadata_batch (array-like) – 1d object array containing a metadata object for each solution.

property archive

The archive which stores solutions generated by this emitter.

Type

ribs.archives.ArchiveBase

property batch_size

Number of solutions to return in ask().

Type

int

property batch_size_dqd

Number of solutions to return in ask_dqd().

This is always 1, as we only return the solution point in ask_dqd().

Type

int

property epsilon

The epsilon added for numerical stability when normalizing gradients in tell_dqd().

Type

int

property itrs

The number of iterations for this emitter.

Type

int

property lower_bounds

(solution_dim,) array with lower bounds of solution space.

For instance, [-1, -1, -1] indicates that every dimension of the solution space has a lower bound of -1.

Type

numpy.ndarray

property restarts

The number of restarts for this emitter.

Type

int

property solution_dim

The dimension of solutions produced by this emitter.

Type

int

property upper_bounds

(solution_dim,) array with upper bounds of solution space.

For instance, [1, 1, 1] indicates that every dimension of the solution space has an upper bound of 1.

Type

numpy.ndarray

property x0

Initial solution for the optimizer.

Type

numpy.ndarray


text:
## Rank-reduction method

Regularization can be implemented as a rank-based constraint (Oropeza and Sacchi, 2011; Trickett, 2008; Cheng and Sacchi, 2015):

 (4)

where denotes the Frobenius norm. denotes a matrix constructed from the frequency slice corresponding to . denotes the noise-free data to be estimated. denotes the estimated signal. denotes the Hankel matrix constructed from . Let , the singular value decomposition of can be expressed as

 (5)

where and are referred to as the left and right singular vector matrices, respectively. is the singular value matrix. denotes complex tranpose. According to equation 4, the rank of the signal component that is embedded in the Hankel matrix is assumed to be . The traditional rank-reduction method based on the truncated singular value decomposition (TSVD) (Oropeza and Sacchi, 2011) can be briefly expressed as

 (6)

which is a solution to equation 4 according to the Eckart-Young-Mirsky theorem (Eckart and Young, 1936). denotes the denoised signal. and are matrices composed of the left singular vectors in and , respectively. is the truncated singular value matrix with the first singular values preserved. Although theoretically equals to the number of distinct dipping components, it is practically defined as a relatively large number considering data complexity, otherwise signal energy can be damaged. The algorithm workflow for the traditional rank-reduction method (RR) is outlined in Algorithm 1. in the algorithm workflow denotes an averaging operator along anti-diagonals.

2020-12-06

format: plain


text:
I'm writing a document in Spanish (with babel), but the name of \tableofcontents is still "Contents". I've tried with \renewcommand{\contentsname}, \addto\captionsspanish and a lot of different combinations but it doesn't work.

I don't know what is happening, because the name of the bibliography is in Spanish, so babel is working properly there.

This is the code I'm using:

\documentclass[11pt,aps,prd,preprintnumbers,nofootinbibn,onecolumn]{revtex4}
\usepackage{graphicx}
\usepackage{dcolumn}
\usepackage{bm}
\usepackage{amssymb}
\usepackage[utf8x]{inputenc}
\usepackage[spanish]{babel}
\usepackage{shapepar}
\usepackage{amsmath}
\usepackage{array}
\usepackage{fancybox}
\usepackage{multirow}
\usepackage{appendix}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{caption}
\usepackage{float}
\usepackage{braket}
\usepackage{amsfonts}
\usepackage{mathrsfs,amsmath}
\usepackage{chemmacros}
\usepackage{bbold}
\usepackage{framed}
\usepackage[usestackEOL]{stackengine}
\usepackage{lipsum}
\usepackage{blindtext}
\usepackage{soul}
\newcommand*\dif{\mathop{}\!\mathrm{d}}
\newcommand*\Dif[1]{\mathop{}\!\mathrm{d^#1}}
\hyphenation{ALPGEN}
\hyphenation{EVTGEN}
\hyphenation{PYTHIA}
\DeclareMathOperator{\Tr}{Tr}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\usepackage{geometry}\geometry{a4paper, total={160mm,247mm}, left=25mm, top=25mm, }
\usepackage{setspace}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{\huge{Título}\\[0.4cm]}
\thispagestyle{empty}

\begin{abstract}
\begin{center}
\today\\
\vspace{1cm}

\hspace{1em}{\bf Autor:}\\
\vspace{0.1cm}
\hspace{1em}NAME $^\ddagger$\\
\vspace{0.8cm}
\end{center}
\hline\vspace{1em}
{\bf Abstract:} \vspace{-0.5em}
\singlespacing
\small{...}\vspace{2em}\hline \vspace{1em}
\scriptsize{$^\ddagger$  E-mail: \texttt{...}
\end{abstract}

\clearpage
\maketitle

\newpage
\thispagestyle{empty}
\spacing{2}
\begin{quotation}
\tableofcontents
\end{quotation}

\section{Introducción}
\setcounter{page}{1}

\begin{thebibliography}{99}
\bibitem{1}
...

\end{thebibliography}
\end{document}

Thank you.

• I've already tried that, but it doesn't work, no variation of \renewcommand{\contentsname} seems to change the name in my document. – TsuKi Jan 8 '17 at 10:16
• Alright, I've a look. Please wrap that long lines with \usepackage{...} at the beginning, that's awful.... You're loading some packages, epsfig is outdated and why manipulating layout parameters whereas you use geometry already? – user31729 Jan 8 '17 at 10:16
• Sorry, I'm new here ... How do I wrap lines? – TsuKi Jan 8 '17 at 10:19
• Using the newline 'enter' key on your keyboard? – user31729 Jan 8 '17 at 10:20
• note size change commands like \small and huge do not take an argument so \small ... not \small{...} commands \bf and \it are deprecated and don't load epsfig unless you need to emulate a document using a package from 1990. – David Carlisle Jan 8 '17 at 10:25

The name of the ToC is stored in \tocname.

Use

\addto\captionsspanish{\renewcommand{\tocname}{Índice}}

instead of \renewcommand{\contentsname}{Índice}}

\documentclass[11pt,aps,prd,preprintnumbers,nofootinbibn,onecolumn]{revtex4}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\begin{document}
\tableofcontents
\section{Introducción}

\end{document}

I kicked all unnecessary (and wrong content) out of the preamble

• Ok, it is working now! The name apperas properly adding that command line. Thank you very much! @Christian Hupfer Do I need to erase all the other packages? Some of them are needed for math equations... – TsuKi Jan 8 '17 at 10:28
• @TsuKi: Just for shortness. Your document was not compilable at all. – user31729 Jan 8 '17 at 10:29
• @TsuKi but only put back the packages that you actually use. It makes no sense at all to have lipsum, blindtext, epsfig in a current math paper and probably not shapepar, stackengine, better to use utf8 than utf8x and only load chemmacros if you are using that chemistry package, etc. – David Carlisle Jan 8 '17 at 11:33
• Belated congratulations on passing the 100k rep mark!! – Mico Jan 10 '17 at 15:21
• Please consider to accept this answer since it was the solution – user31729 Jan 15 '17 at 18:11


text:
Presentation Open Access

# Diversity in DH (2020)

Bordalejo, Barbara; O'Donnell, Daniel

### JSON-LD (schema.org) Export

{
"description": "
One of the main characteristics of work in the Digital Humanities is collaboration: between individual scholars with complementary expertise, across disciplines, and languages, countries, and continents. Many digital humanists have found that academic cultures can differ widely because cultural factors often weigh on the scope and vision of individuals. For this reason, diversity is at the forefront of the Digital Humanities. This workshop aims to make the participants acquainted with different understandings of diversity in different parts of the globe while considering how more diverse teams contribute to the development of our work.
\n\n

\n\n
The workshop is directed at anyone with an interest in understanding diversity in digital humanities and creating a welcoming and inclusive DH environment. Conference organizers, leaders in the field, and those who often form part of hiring committees are invited to participate. Everyone is welcome to attend, but we particularly encourage the participation of people who are in privileged positions in academia, GLAM, or similar environments.
\n\n
The workshop will combine presentations, individual work, and roundtables tackling issues such as:
\n\n

\n\n
· The importance of diversity
\n\n
· Implicit bias
\n\n
· Cultural cloning
\n\n
· Intersectionality
\n\n
· Civil courage
\n\n
· Strategies for becoming more inclusive
\n\n
· Effective collaboration across cultures
\n\n

\n\n
The workshop will cover gender, ethnic, and linguistic diversity, as well as topics such as ableism, cultural diversity, class, and other matters. The important notion of intercultural communication will also be addressed.
\n\n
During these conversations and exercises, we will have a particular focus on the digital humanities as a working environment, but many of the strategies might be transposed to other areas or to the projects that we develop as digital humanists.
",
"creator": [
{
"@id": "https://orcid.org/0000-0001-8255-0265",
"@type": "Person",
"name": "Bordalejo, Barbara"
},
{
"affiliation": "University of Lethbridge",
"@id": "https://orcid.org/0000-0002-0127-4893",
"@type": "Person",
"name": "O'Donnell, Daniel"
}
],
"url": "https://zenodo.org/record/3950437",
"datePublished": "2020-07-17",
"version": "2020",
"keywords": [
"Diversity",
"Equity",
"Intersectionality",
"Digital Humanities",
"Cultural cloning",
"Implicit bias",
"Inclusion"
],
"@context": "https://schema.org/",
"identifier": "https://doi.org/10.5281/zenodo.3950437",
"@id": "https://doi.org/10.5281/zenodo.3950437",
"@type": "PresentationDigitalDocument",
"name": "Diversity in DH (2020)"
}
74
57
views


text:
## GARY PIG GOLD ON BOB DYLAN, A YONGE STREET BAR BAND, AND THE DEATH, 50 YEARS AGO THIS MONTH, OF ROCK AND ROLL

Posted in Opinion, Review with tags , , , , , , , , , , , , , , , , on May 9, 2016 by segarini

As most pretty-pointedly shown throughout Martin Scorsese’s remarkable No Direction Home, the ’66-model Bob Dylan was an American idol at the indisputable peak of his powers as the [insert your own convenient pigeonhole here] Poet/Laureate of a Generation, Crown Prince of the (Thinking Man’s) Hit Parade, or – my personal favorite – Snot-headed, Venom-spewing Anti-Rockstar of All Time.

## Pat Blythe – Toronto’s Mixed Grill – A Scrapbook

Posted in Opinion with tags , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , on March 18, 2015 by segarini

It’s 4am on Sunday morning, March 8, and I’ve just arrived home from a long day and night of music hopping….and the damn Queen streetcar short-turned again….and the clocks went forward one hour (OMG it’s really 5am!!)….and I’ve decided to change my tune (so to speak)….and tell you about my “day in the life of….”  rather than have our esteemed editor post the article I’ve already filed.

## JAIMIE VERNON – GODS OF THE HAMMER

Posted in Opinion with tags , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , on September 6, 2014 by segarini


text:
You are currently browsing the monthly archive for December 2017.

Kaisa Matomaki, Maksym Radziwill, and I have uploaded to the arXiv our paper “Correlations of the von Mangoldt and higher divisor functions II. Divisor correlations in short ranges“. This is a sequel of sorts to our previous paper on divisor correlations, though the proof techniques in this paper are rather different. As with the previous paper, our interest is in correlations such as

$\displaystyle \sum_{n \leq X} d_k(n) d_l(n+h) \ \ \ \ \ (1)$

for medium-sized ${h}$ and large ${X}$, where ${k \geq l \geq 1}$ are natural numbers and ${d_k(n) = \sum_{n = m_1 \dots m_k} 1}$ is the ${k^{th}}$ divisor function (actually our methods can also treat a generalisation in which ${k}$ is non-integer, but for simplicity let us stick with the integer case for this discussion). Our methods also allow for one of the divisor function factors to be replaced with a von Mangoldt function, but (in contrast to the previous paper) we cannot treat the case when both factors are von Mangoldt.

As discussed in this previous post, one heuristically expects an asymptotic of the form

$\displaystyle \sum_{n \leq X} d_k(n) d_l(n+h) = P_{k,l,h}( \log X ) X + O( X^{1/2+\varepsilon})$

for any fixed ${\varepsilon>0}$, where ${P_{k,l,h}}$ is a certain explicit (but rather complicated) polynomial of degree ${k+l-1}$. Such asymptotics are known when ${l \leq 2}$, but remain open for ${k \geq l \geq 3}$. In the previous paper, we were able to obtain a weaker bound of the form

$\displaystyle \sum_{n \leq X} d_k(n) d_l(n+h) = P_{k,l,h}( \log X ) X + O_A( X \log^{-A} X)$

for ${1-O_A(\log^{-A} X)}$ of the shifts ${-H \leq h \leq H}$, whenever the shift range ${H}$ lies between ${X^{8/33+\varepsilon}}$ and ${X^{1-\varepsilon}}$. But the methods become increasingly hard to use as ${H}$ gets smaller. In this paper, we use a rather different method to obtain the even weaker bound

$\displaystyle \sum_{n \leq X} d_k(n) d_l(n+h) = (1+o(1)) P_{k,l,h}( \log X ) X$

for ${1-o(1)}$ of the shifts ${-H \leq h \leq H}$, where ${H}$ can now be as short as ${H = \log^{10^4 k \log k} X}$. The constant ${10^4}$ can be improved, but there are serious obstacles to using our method to go below ${\log^{k \log k} X}$ (as the exceptionally large values of ${d_k}$ then begin to dominate). This can be viewed as an analogue to our previous paper on correlations of bounded multiplicative functions on average, in which the functions ${d_k,d_l}$ are now unbounded, and indeed our proof strategy is based in large part on that paper (but with many significant new technical complications).

We now discuss some of the ingredients of the proof. Unsurprisingly, the first step is the circle method, expressing (1) in terms of exponential sums such as

$\displaystyle S(\alpha) := \sum_{n \leq X} d_k(n) e(\alpha).$

Actually, it is convenient to first prune ${d_k}$ slightly by zeroing out this function on “atypical” numbers ${n}$ that have an unusually small or large number of factors in a certain sense, but let us ignore this technicality for this discussion. The contribution of ${S(\alpha)}$ for “major arc” ${\alpha}$ can be treated by standard techniques (and is the source of the main term ${P_{k,l,h}(\log X) X}$; the main difficulty comes from treating the contribution of “minor arc” ${\alpha}$.

In our previous paper on bounded multiplicative functions, we used Plancherel’s theorem to estimate the global ${L^2}$ norm ${\int_{{\bf R}/{\bf Z}} |S(\alpha)|^2\ d\alpha}$, and then also used the Katai-Bourgain-Sarnak-Ziegler orthogonality criterion to control local ${L^2}$ norms ${\int_I |S(\alpha)|^2\ d\alpha}$, where ${I}$ was a minor arc interval of length about ${1/H}$, and these two estimates together were sufficient to get a good bound on correlations by an application of Hölder’s inequality. For ${d_k}$, it is more convenient to use Dirichlet series methods (and Ramaré-type factorisations of such Dirichlet series) to control local ${L^2}$ norms on minor arcs, in the spirit of the proof of the Matomaki-Radziwill theorem; a key point is to develop “log-free” mean value theorems for Dirichlet series associated to functions such as ${d_k}$, so as not to wipe out the (rather small) savings one will get over the trivial bound from this method. On the other hand, the global ${L^2}$ bound will definitely be unusable, because the ${\ell^2}$ sum ${\sum_{n \leq X} d_k(n)^2}$ has too many unwanted factors of ${\log X}$. Fortunately, we can substitute this global ${L^2}$ bound with a “large values” bound that controls expressions such as

$\displaystyle \sum_{i=1}^J \int_{I_i} |S(\alpha)|^2\ d\alpha$

for a moderate number of disjoint intervals ${I_1,\dots,I_J}$, with a bound that is slightly better (for ${J}$ a medium-sized power of ${\log X}$) than what one would have obtained by bounding each integral ${\int_{I_i} |S(\alpha)|^2\ d\alpha}$ separately. (One needs to save more than ${J^{1/2}}$ for the argument to work; we end up saving a factor of about ${J^{3/4}}$.) This large values estimate is probably the most novel contribution of the paper. After taking the Fourier transform, matters basically reduce to getting a good estimate for

$\displaystyle \sum_{i=1}^J (\int_X^{2X} |\sum_{x \leq n \leq x+H} d_k(n) e(\alpha_i n)|^2\ dx)^{1/2},$

where ${\alpha_i}$ is the midpoint of ${I_i}$; thus we need some upper bound on the large local Fourier coefficients of ${d_k}$. These coefficients are difficult to calculate directly, but, in the spirit of a paper of Ben Green and myself, we can try to replace ${d_k}$ by a more tractable and “pseudorandom” majorant ${\tilde d_k}$ for which the local Fourier coefficients are computable (on average). After a standard duality argument, one ends up having to control expressions such as

$\displaystyle |\sum_{x \leq n \leq x+H} \tilde d_k(n) e((\alpha_i -\alpha_{i'}) n)|$

after various averaging in the ${x, i,i'}$ parameters. These local Fourier coefficients of ${\tilde d_k}$ turn out to be small on average unless ${\alpha_i -\alpha_{i'}}$ is “major arc”. One then is left with a mostly combinatorial problem of trying to bound how often this major arc scenario occurs. This is very close to a computation in the previously mentioned paper of Ben and myself; there is a technical wrinkle in that the ${\alpha_i}$ are not as well separated as they were in my paper with Ben, but it turns out that one can modify the arguments in that paper to still obtain a satisfactory estimate in this case (after first grouping nearby frequencies ${\alpha_i}$ together, and modifying the duality argument accordingly).

In the tradition of “Polymath projects“, the problem posed in the previous two blog posts has now been solved, thanks to the cumulative effect of many small contributions by many participants (including, but not limited to, Sean Eberhard, Tobias Fritz, Siddharta Gadgil, Tobias Hartnick, Chris Jerdonek, Apoorva Khare, Antonio Machiavelo, Pace Nielsen, Andy Putman, Will Sawin, Alexander Shamov, Lior Silberman, and David Speyer). In this post I’ll write down a streamlined resolution, eliding a number of important but ultimately removable partial steps and insights made by the above contributors en route to the solution.

Theorem 1 Let ${G = (G,\cdot)}$ be a group. Suppose one has a “seminorm” function ${\| \|: G \rightarrow [0,+\infty)}$ which obeys the triangle inequality

$\displaystyle \|xy \| \leq \|x\| + \|y\|$

for all ${x,y \in G}$, with equality whenever ${x=y}$. Then the seminorm factors through the abelianisation map ${G \mapsto G/[G,G]}$.

Proof: By the triangle inequality, it suffices to show that ${\| [x,y]\| = 0}$ for all ${x,y \in G}$, where ${[x,y] := xyx^{-1}y^{-1}}$ is the commutator.

We first establish some basic facts. Firstly, by hypothesis we have ${\|x^2\| = 2 \|x\|}$, and hence ${\|x^n \| = n \|x\|}$ whenever ${n}$ is a power of two. On the other hand, by the triangle inequality we have ${\|x^n \| \leq n\|x\|}$ for all positive ${n}$, and hence by the triangle inequality again we also have the matching lower bound, thus

$\displaystyle \|x^n \| = n \|x\|$

for all ${n > 0}$. The claim is also true for ${n=0}$ (apply the preceding bound with ${x=1}$ and ${n=2}$). By replacing ${\|x\|}$ with ${\max(\|x\|, \|x^{-1}\|)}$ if necessary we may now also assume without loss of generality that ${\|x^{-1} \| = \|x\|}$, thus

$\displaystyle \|x^n \| = |n| \|x\| \ \ \ \ \ (1)$

for all integers ${n}$.

Next, for any ${x,y \in G}$, and any natural number ${n}$, we have

$\displaystyle \|yxy^{-1} \| = \frac{1}{n} \| (yxy^{-1})^n \|$

$\displaystyle = \frac{1}{n} \| y x^n y^{-1} \|$

$\displaystyle \leq \frac{1}{n} ( \|y\| + n \|x\| + \|y\|^{-1} )$

so on taking limits as ${n \rightarrow \infty}$ we have ${\|yxy^{-1} \| \leq \|x\|}$. Replacing ${x,y}$ by ${yxy^{-1},y^{-1}}$ gives the matching lower bound, thus we have the conjugation invariance

$\displaystyle \|yxy^{-1} \| = \|x\|. \ \ \ \ \ (2)$

Next, we observe that if ${x,y,z,w}$ are such that ${x}$ is conjugate to both ${wy}$ and ${zw^{-1}}$, then one has the inequality

$\displaystyle \|x\| \leq \frac{1}{2} ( \|y \| + \| z \| ). \ \ \ \ \ (3)$

Indeed, if we write ${x = swys^{-1} = t zw^{-1} t^{-1}}$ for some ${s,t \in G}$, then for any natural number ${n}$ one has

$\displaystyle \|x\| = \frac{1}{2n} \| x^n x^n \|$

$\displaystyle = \frac{1}{2n} \| swy \dots wy s^{-1}t zw^{-1} \dots zw^{-1} t^{-1} \|$

where the ${wy}$ and ${zw^{-1}}$ terms each appear ${n}$ times. From (2) we see that conjugation by ${w}$ does not affect the norm. Using this and the triangle inequality several times, we conclude that

$\displaystyle \|x\| \leq \frac{1}{2n} ( \|s\| + n \|y\| + \| s^{-1} t\| + n \|z\| + \|t^{-1} \| ),$

and the claim (3) follows by sending ${n \rightarrow \infty}$.

The following special case of (3) will be of particular interest. Let ${x,y \in G}$, and for any integers ${m,k}$, define the quantity

$\displaystyle f(m,k) := \| x^m [x,y]^k \|.$

Observe that ${x^m [x,y]^k}$ is conjugate to both ${x (x^{m-1} [x,y]^k)}$ and to ${(y^{-1} x^m [x,y]^{k-1} xy) x^{-1}}$, hence by (3) one has

$\displaystyle \| x^m [x,y]^k \| \leq \frac{1}{2} ( \| x^{m-1} [x,y]^k \| + \| y^{-1} x^{m} [x,y]^{k-1} xy \|)$

which by (2) leads to the recursive inequality

$\displaystyle f(m,k) \leq \frac{1}{2} (f(m-1,k) + f(m+1,k-1)).$

We can write this in probabilistic notation as

$\displaystyle f(m,k) \leq {\bf E} f( (m,k) + X )$

where ${X}$ is a random vector that takes the values ${(-1,0)}$ and ${(1,-1)}$ with probability ${1/2}$ each. Iterating this, we conclude in particular that for any large natural number ${n}$, one has

$\displaystyle f(0,n) \leq {\bf E} f( Z )$

where ${Z := (0,n) + X_1 + \dots + X_{2n}}$ and ${X_1,\dots,X_{2n}}$ are iid copies of ${X}$. We can write ${Z = (1,-1/2) (Y_1 + \dots + Y_{2n})}$ where $Y_1,\dots,Y_{2n} = \pm 1$ are iid signs.  By the triangle inequality, we thus have

$\displaystyle f( Z ) \leq |Y_1+\dots+Y_{2n}| (\|x\| + \frac{1}{2} \| [x,y] \|),$

noting that $Y_1+\dots+Y_{2n}$ is an even integer.  On the other hand, $Y_1+\dots+Y_{2n}$ has mean zero and variance $2n$, hence by Cauchy-Schwarz

$\displaystyle f(0,n) \leq \sqrt{2n}( \|x\| + \frac{1}{2} \| [x,y] \|).$

But by (1), the left-hand side is equal to ${n \| [x,y]\|}$. Dividing by ${n}$ and then sending ${n \rightarrow \infty}$, we obtain the claim. $\Box$

The above theorem reduces such seminorms to abelian groups. It is easy to see from (1) that any torsion element of such groups has zero seminorm, so we can in fact restrict to torsion-free groups, which we now write using additive notation ${G = (G,+)}$, thus for instance ${\| nx \| = |n| \|x\|}$ for ${n \in {\bf Z}}$. We think of ${G}$ as a ${{\bf Z}}$-module. One can then extend the seminorm to the associated ${{\bf Q}}$-vector space ${G \otimes_{\bf Z} {\bf Q}}$ by the formula ${\|\frac{a}{b} x\| := \frac{a}{b} \|x\|}$, and then to the associated ${{\bf R}}$-vector space ${G \otimes_{\bf Z} {\bf R}}$ by continuity, at which point it becomes a genuine seminorm (provided we have ensured the symmetry condition ${\|x\| = \|x^{-1}\|}$). Conversely, any seminorm on ${G \otimes_{\bf Z} {\bf R}}$ induces a seminorm on ${G}$. (These arguments also appear in this paper of Khare and Rajaratnam.)

This post is a continuation of the previous post, which has attracted a large number of comments. I’m recording here some calculations that arose from those comments (particularly those of Pace Nielsen, Lior Silberman, Tobias Fritz, and Apoorva Khare). Please feel free to either continue these calculations or to discuss other approaches to the problem, such as those mentioned in the remaining comments to the previous post.

Let ${F_2}$ be the free group on two generators ${a,b}$, and let ${\| \|: F_2 \rightarrow {\bf R}^+}$ be a quantity obeying the triangle inequality

$\displaystyle \| xy\| \leq \|x \| + \|y\|$

and the linear growth property

$\displaystyle \| x^n \| = |n| \| x\|$

for all ${x,y \in F_2}$ and integers ${n \in {\bf Z}}$; this implies the conjugation invariance

$\displaystyle \| y^{-1} x y \| = \|x\|$

or equivalently

$\displaystyle \| xy \| = \| yx\|$

We consider inequalities of the form

$\displaystyle \| xyx^{-1}y^{-1} \| \leq \alpha \|x\| + \beta \| y\| \ \ \ \ \ (1)$

or

$\displaystyle \| xyx^{-2}y^{-1} \| \leq \gamma \|x\| + \delta \| y\| \ \ \ \ \ (2)$

for various real numbers ${\alpha,\beta,\gamma,\delta}$. For instance, since

$\displaystyle \| xyx^{-1}y^{-1} \| \leq \| xyx^{-1}\| + \|y^{-1} \| = \|y\| + \|y\|$

we have (1) for ${(\alpha,\beta) = (2,0)}$. We also have the following further relations:

Proposition 1

• (i) If (1) holds for ${(\alpha,\beta)}$, then it holds for ${(\beta,\alpha)}$.
• (ii) If (1) holds for ${(\alpha,\beta)}$, then (2) holds for ${(\alpha+1, \frac{\beta}{2})}$.
• (iii) If (2) holds for ${(\gamma,\delta)}$, then (1) holds for ${(\frac{2\gamma}{3}, \frac{2\delta}{3})}$.
• (iv) If (1) holds for ${(\alpha,\beta)}$ and (2) holds for ${(\gamma,\delta)}$, then (1) holds for ${(\frac{2\alpha+1+\gamma}{4}, \frac{\delta+\beta}{4})}$.

Proof: For (i) we simply observe that

$\displaystyle \| xyx^{-1} y^{-1} \| = \| (xyx^{-1} y^{-1})^{-1} \| = \| y^{-1} x^{-1} y x \| = \| y x y^{-1} x^{-1} \|.$

For (ii), we calculate

$\displaystyle \| xyx^{-2}y^{-1} \| = \frac{1}{2}\| (xyx^{-2}y^{-1})^2 \|$

$\displaystyle = \frac{1}{2} \| (xyx^{-2}y^{-1} x) (yx^{-2} y^{-1}) \|$

$\displaystyle \leq \frac{1}{2} (\| xyx^{-2}y^{-1} x\| + \|yx^{-2} y^{-1}\|)$

$\displaystyle \leq \frac{1}{2} ( \| x^2 y x^{-2} y^{-1} \| + 2 \|x\| )$

$\displaystyle \leq \frac{1}{2} ( 2 \alpha \|x\| + \beta \|y\| + 2 \|x\|)$

giving the claim.

For (iii), we calculate

$\displaystyle \| xyx^{-1}y^{-1}\| = \frac{1}{3} \| (xyx^{-1}y^{-1})^3 \|$

$\displaystyle = \frac{1}{3} \| (xyx) (x^{-2} y^{-1} xy) (xyx)^{-1} (x^2 y x^{-1} y^{-1}) \|$

$\displaystyle \leq \frac{1}{3} ( \| x^{-2} y^{-1} xy\| + \| x^2 y x^{-1} y^{-1}\| )$

$\displaystyle = \frac{1}{3} ( \| xy x^{-2} y^{-1} \| + \|x^{-1} y^{-1} x^2 y \| )$

$\displaystyle \leq \frac{1}{3} ( \gamma \|x\| + \delta \|y\| + \gamma \|x\| + \delta \|y\|)$

giving the claim.

For (iv), we calculate

$\displaystyle \| xyx^{-1}y^{-1}\| = \frac{1}{4} \| (xyx^{-1}y^{-1})^4 \|$

$\displaystyle = \frac{1}{4} \| (xy) (x^{-1} y^{-1} x) (y x^{-1} y^{-1}) (xyx^{-1}) (xy)^{-1} (x^2yx^{-1}y^{-1}) \|$

$\displaystyle \leq \frac{1}{4} ( \| (x^{-1} y^{-1} x) (y x^{-1} y^{-1}) (xyx^{-1}) \| + \|x^2yx^{-1}y^{-1}\| )$

$\displaystyle \leq \frac{1}{4} ( \|(y x^{-1} y^{-1}) (xy^{-1}x^{-1})(x^{-1} y x) \| + \gamma \|x\| + \delta \|y\|)$

$\displaystyle \leq \frac{1}{4} ( \|x\| + \|(xy^{-1}x^{-1})(x^{-1} y x) \| + \gamma \|x\| + \delta \|y\|)$

$\displaystyle = \frac{1}{4} ( \|x\| + \|x^{-2} y x^2 y^{-1} \|+ \gamma \|x\| + \delta \|y\|)$

$\displaystyle \leq \frac{1}{4} ( \|x\| + 2\alpha \|x\| + \beta \|y\| + \gamma \|x\| + \delta \|y\|)$

giving the claim. $\Box$

Here is a typical application of the above estimates. If (1) holds for ${(\alpha,\beta)}$, then by part (i) it holds for ${(\beta,\alpha)}$, then by (ii) (2) holds for ${(\beta+1,\frac{\alpha}{2})}$, then by (iv) (1) holds for ${(\frac{3\beta+2}{4}, \frac{3\alpha}{8})}$. The map ${(\alpha,\beta) \mapsto (\frac{3\beta+2}{4}, \frac{3\alpha}{8})}$ has fixed point ${(\alpha,\beta) = (\frac{16}{23}, \frac{6}{23})}$, thus

$\displaystyle \| xyx^{-1}y^{-1} \| \leq \frac{16}{23} \|x\| + \frac{6}{23} \|y\|.$

For instance, if ${\|a\|, \|b\| \leq 1}$, then ${\|aba^{-1}b^{-1} \| \leq 22/23 = 0.95652\dots}$.

Here is a curious question posed to me by Apoorva Khare that I do not know the answer to. Let ${F_2}$ be the free group on two generators ${a,b}$. Does there exist a metric ${d}$ on this group which is

• bi-invariant, thus ${d(xg,yg)=d(gx,gy) = d(x,y)}$ for all ${x,y,g \in F_2}$; and
• linear growth in the sense that ${d(x^n,1) = n d(x,1)}$ for all ${x \in F_2}$ and all natural numbers ${n}$?

By defining the “norm” of an element ${x \in F_2}$ to be ${\| x\| := d(x,1)}$, an equivalent formulation of the problem asks if there exists a non-negative norm function ${\| \|: F_2 \rightarrow {\bf R}^+}$ that obeys the conjugation invariance

$\displaystyle \| gxg^{-1} \| = \|x \| \ \ \ \ \ (1)$

for all ${x,g \in F_2}$, the triangle inequality

$\displaystyle \| xy \| \leq \| x\| + \| y\| \ \ \ \ \ (2)$

for all ${x,y \in F_2}$, and the linear growth

$\displaystyle \| x^n \| = |n| \|x\| \ \ \ \ \ (3)$

for all ${x \in F_2}$ and ${n \in {\bf Z}}$, and such that ${\|x\| > 0}$ for all non-identity ${x \in F_2}$. Indeed, if such a norm exists then one can just take ${d(x,y) := \| x y^{-1} \|}$ to give the desired metric.

One can normalise the norm of the generators to be at most ${1}$, thus

$\displaystyle \| a \|, \| b \| \leq 1.$

This can then be used to upper bound the norm of other words in ${F_2}$. For instance, from (1), (3) one has

$\displaystyle \| aba^{-1} \|, \| b^{-1} a b \|, \| a^{-1} b^{-1} a \|, \| bab^{-1}\| \leq 1.$

A bit less trivially, from (3), (2), (1) one can bound commutators as

$\displaystyle \| aba^{-1} b^{-1} \| = \frac{1}{3} \| (aba^{-1} b^{-1})^3 \|$

$\displaystyle = \frac{1}{3} \| (aba^{-1}) (b^{-1} ab) (a^{-1} b^{-1} a) (b ab^{-1}) \|$

$\displaystyle \leq \frac{4}{3}.$

In a similar spirit one has

$\displaystyle \| aba^{-2} b^{-1} \| = \frac{1}{2} \| (aba^{-2} b^{-1})^2 \|$

$\displaystyle = \frac{1}{2} \| (aba^{-1}) (a^{-1} b^{-1} a) (ba^{-1} b^{-1}) (ba^{-1} b^{-1}) \|$

$\displaystyle \leq 2.$

What is not clear to me is if one can keep arguing like this to continually improve the upper bounds on the norm ${\| g\|}$ of a given non-trivial group element ${g}$ to the point where this norm must in fact vanish, which would demonstrate that no metric with the above properties on ${F_2}$ would exist (and in fact would impose strong constraints on similar metrics existing on other groups as well). It is also tempting to use some ideas from geometric group theory (e.g. asymptotic cones) to try to understand these metrics further, though I wasn’t able to get very far with this approach. Anyway, this feels like a problem that might be somewhat receptive to a more crowdsourced attack, so I am posing it here in case any readers wish to try to make progress on it.

The Boussinesq equations for inviscid, incompressible two-dimensional fluid flow in the presence of gravity are given by

$\displaystyle (\partial_t + u_x \partial_x+ u_y \partial_y) u_x = -\partial_x p \ \ \ \ \ (1)$

$\displaystyle (\partial_t + u_x \partial_x+ u_y \partial_y) u_y = \rho - \partial_y p \ \ \ \ \ (2)$

$\displaystyle (\partial_t + u_x \partial_x+ u_y \partial_y) \rho = 0 \ \ \ \ \ (3)$

$\displaystyle \partial_x u_x + \partial_y u_y = 0 \ \ \ \ \ (4)$

where ${u: {\bf R} \times {\bf R}^2 \rightarrow {\bf R}^2}$ is the velocity field, ${p: {\bf R} \times {\bf R}^2 \rightarrow {\bf R}}$ is the pressure field, and ${\rho: {\bf R} \times {\bf R}^2 \rightarrow {\bf R}}$ is the density field (or, in some physical interpretations, the temperature field). In this post we shall restrict ourselves to formal manipulations, assuming implicitly that all fields are regular enough (or sufficiently decaying at spatial infinity) that the manipulations are justified. Using the material derivative ${D_t := \partial_t + u_x \partial_x + u_y \partial_y}$, one can abbreviate these equations as

$\displaystyle D_t u_x = -\partial_x p$

$\displaystyle D_t u_y = \rho - \partial_y p$

$\displaystyle D_t \rho = 0$

$\displaystyle \partial_x u_x + \partial_y u_y = 0.$

One can eliminate the role of the pressure ${p}$ by working with the vorticity ${\omega := \partial_x u_y - \partial_y u_x}$. A standard calculation then leads us to the equivalent “vorticity-stream” formulation

$\displaystyle D_t \omega = \partial_x \rho$

$\displaystyle D_t \rho = 0$

$\displaystyle \omega = \partial_x u_y - \partial_y u_x$

$\displaystyle \partial_x u_y + \partial_y u_y = 0$

of the Boussinesq equations. The latter two equations can be used to recover the velocity field ${u}$ from the vorticity ${\omega}$ by the Biot-Savart law

$\displaystyle u_x := -\partial_y \Delta^{-1} \omega; \quad u_y = \partial_x \Delta^{-1} \omega.$

It has long been observed (see e.g. Section 5.4.1 of Bertozzi-Majda) that the Boussinesq equations are very similar, though not quite identical, to the three-dimensional inviscid incompressible Euler equations under the hypothesis of axial symmetry (with swirl). The Euler equations are

$\displaystyle \partial_t u + (u \cdot \nabla) u = - \nabla p$

$\displaystyle \nabla \cdot u = 0$

where now the velocity field ${u: {\bf R} \times {\bf R}^3 \rightarrow {\bf R}^3}$ and pressure field ${p: {\bf R} \times {\bf R}^3 \rightarrow {\bf R}}$ are over the three-dimensional domain ${{\bf R}^3}$. If one expresses ${{\bf R}^3}$ in polar coordinates ${(z,r,\theta)}$ then one can write the velocity vector field ${u}$ in these coordinates as

$\displaystyle u = u^z \frac{d}{dz} + u^r \frac{d}{dr} + u^\theta \frac{d}{d\theta}.$

If we make the axial symmetry assumption that these components, as well as ${p}$, do not depend on the ${\theta}$ variable, thus

$\displaystyle \partial_\theta u^z, \partial_\theta u^r, \partial_\theta u^\theta, \partial_\theta p = 0,$

then after some calculation (which we give below the fold) one can eventually reduce the Euler equations to the system

$\displaystyle \tilde D_t \omega = \frac{1}{r^4} \partial_z \rho \ \ \ \ \ (5)$

$\displaystyle \tilde D_t \rho = 0 \ \ \ \ \ (6)$

$\displaystyle \omega = \frac{1}{r} (\partial_z u^r - \partial_r u^z) \ \ \ \ \ (7)$

$\displaystyle \partial_z(ru^z) + \partial_r(ru^r) = 0 \ \ \ \ \ (8)$

where ${\tilde D_t := \partial_t + u^z \partial_z + u^r \partial_r}$ is the modified material derivative, and ${\rho}$ is the field ${\rho := (r u^\theta)^2}$. This is almost identical with the Boussinesq equations except for some additional powers of ${r}$; thus, the intuition is that the Boussinesq equations are a simplified model for axially symmetric Euler flows when one stays away from the axis ${r=0}$ and also does not wander off to ${r=\infty}$.

However, this heuristic is not rigorous; the above calculations do not actually give an embedding of the Boussinesq equations into Euler. (The equations do match on the cylinder ${r=1}$, but this is a measure zero subset of the domain, and so is not enough to give an embedding on any non-trivial region of space.) Recently, while playing around with trying to embed other equations into the Euler equations, I discovered that it is possible to make such an embedding into a four-dimensional Euler equation, albeit on a slightly curved manifold rather than in Euclidean space. More precisely, we use the Ebin-Marsden generalisation

$\displaystyle \partial_t u + \nabla_u u = - \mathrm{grad}_g p$

$\displaystyle \mathrm{div}_g u = 0$

of the Euler equations to an arbitrary Riemannian manifold ${(M,g)}$ (ignoring any issues of boundary conditions for this discussion), where ${u: {\bf R} \rightarrow \Gamma(TM)}$ is a time-dependent vector field, ${p: {\bf R} \rightarrow C^\infty(M)}$ is a time-dependent scalar field, and ${\nabla_u}$ is the covariant derivative along ${u}$ using the Levi-Civita connection ${\nabla}$. In Penrose abstract index notation (using the Levi-Civita connection ${\nabla}$, and raising and lowering indices using the metric ${g = g_{ij}}$), the equations of motion become

$\displaystyle \partial_t u^i + u^j \nabla_j u^i = - \nabla^i p \ \ \ \ \ (9)$

$\displaystyle \nabla_i u^i = 0;$

in coordinates, this becomes

$\displaystyle \partial_t u^i + u^j (\partial_j u^i + \Gamma^i_{jk} u^k) = - g^{ij} \partial_j p$

$\displaystyle \partial_i u^i + \Gamma^i_{ik} u^k = 0 \ \ \ \ \ (10)$

where the Christoffel symbols ${\Gamma^i_{jk}}$ are given by the formula

$\displaystyle \Gamma^i_{jk} := \frac{1}{2} g^{il} (\partial_j g_{lk} + \partial_k g_{lj} - \partial_l g_{jk}),$

where ${g^{il}}$ is the inverse to the metric tensor ${g_{il}}$. If the coordinates are chosen so that the volume form ${dg}$ is the Euclidean volume form ${dx}$, thus ${\mathrm{det}(g)=1}$, then on differentiating we have ${g^{ij} \partial_k g_{ij} = 0}$, and hence ${\Gamma^i_{ik} = 0}$, and so the divergence-free equation (10) simplifies in this case to ${\partial_i u^i = 0}$. The Ebin-Marsden Euler equations are the natural generalisation of the Euler equations to arbitrary manifolds; for instance, they (formally) conserve the kinetic energy

$\displaystyle \frac{1}{2} \int_M |u|_g^2\ dg = \frac{1}{2} \int_M g_{ij} u^i u^j\ dg$

and can be viewed as the formal geodesic flow equation on the infinite-dimensional manifold of volume-preserving diffeomorphisms on ${M}$ (see this previous post for a discussion of this in the flat space case).

The specific four-dimensional manifold in question is the space ${{\bf R} \times {\bf R}^+ \times {\bf R}/{\bf Z} \times {\bf R}/{\bf Z}}$ with metric

$\displaystyle dx^2 + dy^2 + y^{-1} dz^2 + y dw^2$

and solutions to the Boussinesq equation on ${{\bf R} \times {\bf R}^+}$ can be transformed into solutions to the Euler equations on this manifold. This is part of a more general family of embeddings into the Euler equations in which passive scalar fields (such as the field ${\rho}$ appearing in the Boussinesq equations) can be incorporated into the dynamics via fluctuations in the Riemannian metric ${g}$). I am writing the details below the fold (partly for my own benefit).


text:
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 4 (Page No. 125)

145 views
Most languages are case sensitive, so keywords can be written only one way, and the regular expressions describing their lexeme is very simple. However, some languages, like SQL, are case insensitive, so a keyword can be written either in lowercase or in uppercase, or in any mixture of cases. Thus, the SQL keyword SELECT can also be written select, Select, or sElEcT, for instance. Show how to write a regular expression for a keyword in a case-insensitive language.  Illustrate the idea by writing the expression for "select" in SQL.

Related questions

1
220 views
Describe the languages denoted by the following regular expressions: $a(a\mid b)^{\ast}a.$ $((\epsilon\mid a)b^{\ast})^{\ast}.$ $(a\mid b)^{\ast}a(a\mid b)(a\mid b).$ $a^{\ast}ba^{\ast}ba^{\ast}ba^{\ast}.$ $(aa\mid bb)^{\ast}((ab\mid ba)(aa\mid bb)^{\ast}(ab\mid ba)(aa\mid bb)^{\ast})^{\ast}.$
Repeat Exercise 4.3.1 on the following grammars: $S\rightarrow SS+\mid SS\: \ast\mid a$ $S\rightarrow 0S1\mid 01$ $S\rightarrow S ( S ) S\mid \epsilon$ $S\rightarrow (L)\mid a$ and $L\rightarrow L,S\mid S$ ... $bterm\rightarrow bterm\:and\:bfactor\mid bfactor$ $bfactor\rightarrow not\: bfactor\mid ( bexpr )\mid true \mid false$
The following is a grammar for regular expressions over symbols $a$ and $b$ only, using $+$ in place of $\mid$ for union, to avoid conflict with the use of vertical bar as a metasymbol in grammars: $rexpr\rightarrow rexpr+rterm\mid rterm$ ... -down parsing? In addition to left factoring, eliminate left recursion from the original grammar. Is the resulting grammar suitable for top-down parsing?


text:
# Why does the reduction of naphthalene with nickel/hydrogen lead to trans-decalin?

Why does the reduction of naphthalene using $$\ce{H2/Ni}$$ lead to trans-decalin instead of cis-decalin?

I learned in high school that catalytic hydrogenations are always syn. Why is this inconsistent with what I learned?

• Because what you learned in high school is an oversimplification. This statement from Chem. Absts.: ”The reduced NiO-MoO3/Al2O3 catalyst at 350° and 35 bar produced the highest decalin yield, i.e., 40 wt.% trans- and 15 wt.% cis-decalin”. Dec 15, 2021 at 21:43
• A similar question about this diagram is on ChemSE. Look here Dec 16, 2021 at 2:56
• @user55119 Even with that simplification ('all' instead of 'some' trans-decalin) the question still remains why trans-decalin is generated at all. My initial assumption is that the bridge is not hydrogenated in a single step which leads to steric effects causing the hydrogens on either end to be installed in different directions but I haven't checked the literature.
– Jan
Dec 16, 2021 at 15:45
• This is because trans decalin is more stable than cis decalin. In cis decalin, 1,3-diaxial interactions (which are repulsive in case of decalin ) destabilize roughly by 8.4kJ/mol than trans decalin. Dec 21, 2021 at 16:12

I think to understand heterogenious hydrogenation you need to understand homogenious hydrogenation of metals by Wilkinson's cataylst and hydroformylation of alkenes by a mixture of hydrogen and carbon monoxide using a cobalt carbonyl cataylst. If we consider for a moment the reaction of an acetylene with a complex such as RuHCl(CO)(PPh3)2. Then what will happen is that the acetylene will bond to the vaccent site on the ruthenium to form a pi complex. Next a rearrangement known as an insertion reaction will occur which will convet the acetylene into a vinyl group. The metal and the hydrogen which was originally on the metal will be attached to the alkene such that they will be cis to each other. This is the basis of why the hydrogenation of an alkyne normally gives the cis isomer with things like partly poisoned palladium.

If we consider for a moment the reaction in the oxo process then we have a hydrogenation with a little bit added onto it. Here is the cycle for cobalt.

The hydrogenation cycle for Wilkinson's cataylst is very similar, you are likely to be thinking of the same sort of thing occuring on the nickel surface. Based on what we know about the chemistry of acetylenes with hydride complexes we can feel confident that an isolated alkene or acetylene will undergo cis hydrogenation. Please see the following picture. What will happen with your substrate is that the very unreactive benzene ring will hydrogenate once to form a very reactive 1,3-diene which will hydrogenate very quickly.

A lot of the selectivity for hydroformylation (linear vs branched product) relates to the energies of the alkyl complexes which exist in part of the cycle.

There are three homogenous hydrogenation mechanisms which exist but the one for Wilkinson's cataylst is the most common and it is the closest to what happens on a nickel or palladium surface.

Now for the 1,3-diene I am sure that as it goes through the hydrogenation process that at some point it will pass through an alkyl complex. This is likely to be in the final stage of the hydrogenation.

The lower energy one will be the main one in the reaction mixture. We need to be careful as the platinum gave the other product. The problem is that when we change from a first row to third row transition metal is the bond energies change. It is possible for the rate determining step to be different even if the catatyltic cycle looks the same. Consider the Monsanto process for the carbonylation of methanol vs the iridium process for the same reaction (even the same substrates) which BP invented later. There the RDS is a different step in the cycle.

I hope that I am not too heavy going, you have just had the associate prof level of answer for the problem.


text:
# Can you increase data rate by increasing number of bits? [closed]

My question is on data rate and baud rate.

data rate = baud rate * n

The question is, can you keep on increasing the data rate by increasing baud rate or number of bits.

I believe it can be increased by increasing the baud rate but what about the latter part?

• What is this $n$ in your formula? This makes no sense to me. The baud rate is usually higher than the data rate. Please explain. Jul 25 '15 at 17:11
• please also add the units you use for each term. Jul 25 '15 at 17:18
• Data Signalling Rate is also known as gross bit rate. So I guess yeah with the increase in bit rate, data rate will increase. Jul 25 '15 at 17:19

maximum data rate [bit/s] = $2H\cdot log_{2}(V)$
Where $H$ is the bandwidth in $Hz$ and $V$ is the number of symbol values.
maximum data rate [bit/s] = $H\cdot log_{2}(1 + S/N)$
Where $S$ is the signal strength and $N$ is the noise level.


text:
Decrement Operators in Belief Change

Decrement Operators in Belief Change

Kai Sauerwald\orcidID0000-0002-1551-7016 FernUniversität in Hagen, 58084 Hagen, Germany
11email: {kai.sauerwald,christoph.beierle}@fernuni-hagen.de
Christoph Beierle FernUniversität in Hagen, 58084 Hagen, Germany
11email: {kai.sauerwald,christoph.beierle}@fernuni-hagen.de
Abstract

While research on iterated revision is predominant in the field of iterated belief change, the class of iterated contraction operators received more attention in recent years. In this article, we examine a non-prioritized generalisation of iterated contraction. In particular, the class of weak decrement operators is introduced, which are operators that by multiple steps achieve the same as a contraction. Inspired by Darwiche and Pearl’s work on iterated revision the subclass of decrement operators is defined. For both, decrement and weak decrement operators, postulates are presented and for each of them a representation theorem in the framework of total preorders is given. Furthermore, we present two types of decrement operators which have a unique representative.

Keywords:
belief revision, belief contraction, non-prioritized change, gradual change, forgetting, decrement operator
\pdfstringdefDisableCommands

1 Introduction

Changing beliefs in a rational way in the light of new information is one of the core abilities of an agent - and thus one of the main concerns of artificial intelligence. The established AGM theory [1] deals with desirable properties of rational belief change. The AGM approach provides properties for different types of belief changes. If new beliefs are incorporated into an agent’s beliefs while maintaining consistency, this is called a revision. Expansion adds a belief unquestioned to an agent’s beliefs, and contraction removes a belief from an agent’s beliefs. Building upon the characterisations of these kinds of changes and the underlying principle of minimal change, the theory fanned out in different directions and sub-fields.

The field of iterated belief revision examines the properties of belief revision operators which, due to their nature, can be applied iteratively. In this sub-field, one of the most influential articles is the seminal paper [7] by Darwiche and Pearl (DP), establishing the insight that belief sets are not a sufficient representation for iterated belief revision. An agent has to encode more information about her belief change strategy into her epistemic state - where the revision strategy deeply corresponds with conditional beliefs. This requires additional postulates that guarantee intended behaviour in forthcoming changes. The common way of encoding, also established by Darwiche and Pearl [7], is an extension of Katsuno and Mendelzon’s characterisation of AGM revision in terms of plausibility orderings [10], where it is assumed that the epistemic states contain an order of the worlds (or interpretations).

Similar work has been done in recent years for iterated contraction. Chopra, Ghose, Meyer and Wong [6] contributed postulates for contraction on epistemic states. Caridroit, Konieczny and Marquis [4] provided postulates for iterated contraction on epistemic states and a characterisation with plausibility orders in the style of Katsuno and Mendelzon. By this characterisation, the main characteristic of a contraction with is that the worlds of the previous state remain plausible and that the most plausible counter-models of become plausible.

However, in the sub-field of non-prioritised belief change, or more specifically, in the field of gradual belief change much work remains to be done on contraction. An important generalisation of iterated revision operators are the class of improvement operators by Konieczny and Pino Pérez [12], which achieve the state of an revision by multiple steps in a gradual way. These kind of changes where intensively studied by Konieczny, Pino Pérez, Booth, Fermé and Grespan [11, 3]. A counterpart of improvement operators for the case of contraction is missing. This article fills this gap. We investigate the contraction analogon to improvement operators, which we call decrement operators. The leading idea is to examine a class of operators which lead, after enough consecutive applications, to the same states as an (iterative) contraction would do.

The research presented in this paper is also motivated by the quest for a formalisation of forgetting operators within the field of knowledge representation and reasoning (KRR). In a recent survey article by Eiter and Kern-Isberner [8] the connection between contraction and forgetting of a belief is dealt with from a KRR point of view. Steps towards a general framework for kinds of forgetting in common-sense based belief management, revealing links to well-known KRR methods, are taken in [2]. However, for the fading out of rarely used beliefs that takes places in humans gradually over time, or for the change of routines, e.g. in established workflows, often requiring many iterations and the intentional forgetting of the previous routines, counterparts in the formal methods of KRR are missing. With our work on decrement operators, we provide some basic building blocks that may prove useful for developing a formalisation of these psychologically inspired forgetting operations.

In summary, the main contributions of this paper are111The full proofs for all theorems given here can be found in the appendix.:

• Postulates for operators which allow to perform contractions gradually.

• Representation theorems for these classes in the framework or epistemic states and total preorders.

• Two types of decrement operators with unique representatives.

The rest of the paper is organised as follows. Section 2 briefly presents the required background on belief change. Section 3 introduces the main idea and the postulates along with a representation theorem for weak decrement operators. In Section 4 the weak decrement operators are restricted by DP-like iteration postulates, leading to the class of decrement operators; we give also a representation theorem for the class of decrement operators. In Section 5 two special types of decrement operators are specified. We close the paper with a discussion and point out future work in Section 6.

2 Background

Let be a propositional signature (non empty finite set of propositional variables). The propositional language is the smallest set, such that for every and , if . We omit often and write instead of . We write formulas in with lower Greek letters , propositional variables with lower case letters , abbreviate by and sometimes write for . The set of the usual propositional interpretations is identified with the set of corresponding complete conjunctions, also called worlds, over . Propositional entailment is denoted by , and is the deductive closure of . This is lifted to a set by defining . For a set of worlds and a total preorder (reflexive and transitive relation) over , we denote with the set of all worlds in the lowest layer of that are elements in . For a total preorder , we denote with its strict variant, i.e. iff and ; with the direct successor variant, i.e. iff and there is no such that ; and we write iff and .

2.1 Epistemic States and Belief Changes

Every agent is equipped with an epistemic state, sometimes also called belief state, that maintains all necessary information for her belief apparatus. With we denote the set of all epistemic states. Without defining what a epistemic state is, we assume that for every epistemic state we can obtain the set of plausible sentences of , which is deductively closed. For the purpose of this article, the set can be represented by a single propositional formula and we will switch between these two representations as needed. We write iff and we define . A belief change operator over is a (left-associative) function . We denote with the n-times application of by to [12].

Darwiche and Pearl [7] propose that an epistemic state should be equipped with an ordering of the worlds (interpretations), where the compatibility with is ensured by the so-called faithfulness. A mapping is called faithful assignment if the following is satisfied [10]:

 if ω1∈\llbracketΨ\rrbracket and ω2∈\llbracketΨ\rrbracket, then ω1≃Ψω2 if ω1∈\llbracketΨ\rrbracket and ω2∉\llbracketΨ\rrbracket, then ω1≤Ψω2 if ≤Ψ=≤Φ, then \llbracketΨ\rrbracket=\llbracketΦ\rrbracket

Konieczny and Pino Pérez give a stronger variant of faithful assignments for iterated belief change [12], which ensures that the mapping is compatible with the belief change operator with respect to syntax independence.

Definition 1 (Strong Faithful Assignment [12])

Let be a belief change operator. A function that maps each epistemic state to a total preorder on interpretations is said to be a strong faithful assigment with respect to if:

 if ω1∈\llbracketΨ\rrbracket and ω2∈\llbracketΨ\rrbracket, then ω1≃Ψω2 (SFA1) if ω1∈\llbracketΨ\rrbracket and ω2∉\llbracketΨ\rrbracket, then ω1≤Ψω2 (SFA2) if α1≡β1,…,αn≡βn, then ≤Ψ∘α1∘…∘αn=≤Ψ∘β1∘…∘βn (SFA3)

We will make use of strong faithful assignments for the characterisation of decrement operators.

2.2 Iterated Contraction

Postulates for AGM contraction in the framework of epistemic states where given by Chopra, Ghose, Meyer and Wong [6], and by Caridroit, Konieczny and Marquis [4] for propositional formula. We give here the formulation by Chropra et al. [6]:

 Bel(Ψ−α)⊆Bel(Ψ) (C1) if α∉Bel(Ψ), then Bel(Ψ)⊆Bel(Ψ−α) (C2) if α≢⊤, then α∉Bel% (Ψ−α) (C3) if α∈Bel(Ψ), then %Bel(Ψ)⊆Cn(Bel(Ψ−α)∪α) (C4) if α≡β, then Bel(Ψ−α)=Bel(Ψ−β) (C5) Bel(Ψ−α)∩Bel(Ψ−β)⊆Bel(Ψ−(α∧β)) (C6) if β∉Bel(Ψ−(α∧β)), then Bel(Ψ−(α∧β))⊆Bel(Ψ−β) (C7)

For an explanation of these postulates we refer to the article of Caridroit et al. [4], where also a characterisation in terms of total preorders is given.

Proposition 1 (AGM Contraction for Epistemic State [4])

A belief change operator fulfils the postulates (C1) to (C7) if and only if there is a faithful assignment such that:

 \llbracketΨ−α\rrbracket=\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ)

In addition to the postulates (C1) to (C7), Konieczny and Pino Pérez give DP-like postulates for intended iteration behaviour of contraction [13]. In the following, we call these class of operators iterated contraction operators, which are characterized by the following proposition.

Proposition 2 (Iterated Contraction[13])

A belief change operator is an iterated contraction operator if and only there exists a faithful assignment such that the following is satisfied:

 if ω1,ω2∈\llbracketα\rrbracket%,thenω1≤Ψω2⇔ω1≤Ψ∘αω2 if ω1,ω2∈\llbracket¬α\rrbracket, then ω1≤Ψω2⇔ω1≤Ψ∘αω2 if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω1<Ψω2⇒ω1<Ψ∘αω2 if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω1≤Ψω2⇒ω1≤Ψ∘αω2

2.3 Improvement Operators

The idea of (weak) improvements is to split the process of an AGM revision for epistemic states [7, p. 7ff] into multiple steps of an operator . For such a gradual operator define , where is smallest integer such that . In the initial paper about improvement operators [12], Konieczny and Pino Pérez gave postulates for , such that is an AGM revision for epistemic states. Due to space reasons, we refer the interested reader to the original paper for the postulates [12]. The following representation theorem gives an impression on weak improvement operators.

Proposition 3 (Weak Improvement Operator[12, Thm. 1])

A belief change operator is a weak improvement operator if and only if there exists a strong faithful assignment such that:

 \llbracketΨ⋅α\rrbracket=min(\llbracketα\rrbracket,≤Ψ)

Furthermore, the class of weak improvement operators is restricted by DP-like iteration postulates [12] to an unique operator. Again, we refer to the work of Konieczny and Pino Pérez [12] for these postulates, and only present the characterisation in the framework of total preorders.

Proposition 4 (Improvement Operator[12, Thm. 2])

A weak improvement operator is an improvement operator if and only there exists a strong faithful assignment which fulfils

 if ω1,ω2∈\llbracketα\rrbracket%,thenω1≤Ψω2⇔ω1≤Ψ□αω2 (S1) if ω1,ω2∈\llbracket¬α\rrbracket, then ω1≤Ψω2⇔ω1≤Ψ□αω2 (S2) if ω1∈\llbracketα\rrbracket and ω2∈\llbracket¬α\rrbracket, then ω1≤Ψω2⇒ω1<Ψ□αω2 (S3) if ω1∈\llbracketα\rrbracket and ω2∈\llbracket¬α\rrbracket, then ω1<Ψω2⇒ω1≤Ψ□αω2 (S4) if ω1∈\llbracketα\rrbracket and ω2∈\llbracket¬α\rrbracket, then ω2≪Ψω1⇒ω1≤Ψ□αω2 (S5)

and satisfies:

 \llbracketΨ⋅α\rrbracket=min(\llbracketα\rrbracket,≤Ψ)

In the following section we use the basic ideas of (weak) improvement operators as a starting point for developing the weak decrement operators.

3 Weak Decrement Operators

A property of a contraction operator is that the success condition of contraction is instantaneously achieved, i.e., if is believed in a state () then after the contraction with , it is not believed any more (). As a generalisation, we define hesitant contractions as operators who achieve the success condition of contraction after multiple consecutive applications.

Definition 2

A belief change operator is called a hesitant contraction operator if the following postulates are fulfilled:

 if α≢⊤, then there exists n∈N0 such that α∉Bel(Ψ∘nα) (hesitant success)

If is an hesitant contraction operator, then we define a corresponding operator by , where if , otherwise is the smallest integer such that .

The following Example 1 shows an modelling application for hesitant belief change operators.

Example 1

Addison bought a new mobile with much easier handling. She does no longer have to press a sequence of buttons to access her favourite application. However, it takes multiple changes of her epistemic state before she contracts the belief of having to press the sequence of buttons for her favourite application.

We now introduce weak decrement operators, which fulfil AGM-like contraction postulates, adapted for the decrement of beliefs.

Definition 3 (Weak Decrement Operator)

A belief change operator is called a weak decrement operator if the following postulates are fulfilled:

 Bel(Ψ∙α)⊆Bel(Ψ) (D1) if α∉Bel(Ψ), then Bel(Ψ)⊆Bel(Ψ∙α) (D2) ∘ is a hesitant\ contraction operator (D3) Bel(Ψ)⊆Cn(Bel(Ψ∙α)∪{α}) (D4) (D5) Bel(Ψ∙α)∩Bel(Ψ∙β)⊆Bel(Ψ∙(α∧β)) (D6) if β∉Bel(Ψ∙(α∧β)), then Bel(Ψ∙(α∧β))⊆Bel(Ψ∙β) (D7)

The postulates (D1) to (D7) correspond to the postulates (C1) to (C7). By (D1) a weak decrement does not add new beliefs, and together with (D2) the beliefs of an agent are not changed if is not believed priorly. (D3) ensures that after enough consecutive application a belief is removed. (D4) is the recovery postulate, stating that removing and then adding again recovers all initial beliefs. The postulate (D5) ensures syntax independence in the case of iteration. (D6) and (D7) state that a contraction of a conjunctive belief is constrained by the results of the contractions with each of the conjuncts alone.

For the class of weak decrement operators the following representation theorem holds:

Theorem 3.1 (Representation Theorem for Weak Decrement Operators)

Let be a belief change operator. Then the following items are equivalent:

1. is a weak decrement operator

2. there exists a strong faithful assignment with respect to such that:

 there exists n∈N0 such that \llbracketΨ∘nα\rrbracket=\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ) and n is the smallest integer such that \llbracketΨ∘nα\rrbracket⊈\llbracketα\rrbracket (decrement success)

From Theorem 3.1 we easily get the following corollary:

Corollary 1

If is a weak decrement operator, then fulfils (C1) to (C7). Furthermore, every belief change operator that fulfils (C1) to (C7) and (D5) is a weak decrement operator.

This shows that weak decrement operators are (up to (D5)) a generalisation of AGM contraction for epistemic states in the sense of Proposition 1.

4 Decrement Operators

We now introduce an ordering on the formulas in order to shorten our notion in the following postulates.

Definition 4

Let be a hesitant change operator, then we define for every epistemic state and every two formula :

 α⪯∘Ψβ iff Bel(Ψ∙αβ)⊆Bel(Ψ∙α)

With we denote the strict variant of and define if and there is no such that .

Intuitively means that in the state the agent is more willing to remove the belief than the belief .

For the iteration of decrement operators we give the following postulates:

 if ¬β⊨α, then Bel(Ψ∘α∙β)=Bel(Ψ∙β) (D8)

(D8) states that a prior decrement with does not influence the beliefs of an decrement with if .

 if ¬β⊨¬α, then Bel(Ψ∘α∙β)=Bel(Ψ∙β) (D9)

(D9) states that a prior decrement with does not influence the beliefs of an decrement with if .

 if α¬γ⊨β, then Ψ∘α∙β⊨γ⇒Ψ∙β⊨γ (D10)

The postulate (D10) states that if a belief in is believed after a decrement of and the removal of , then only a removal of does not influence the belief in if implies .

 if γα≡⊥, then Ψ∙β⊨γ ⇒ Ψ∘α∙β⊨γ (D11)

By (D11), if and do not share anything, then a decrease of does not influence this belief.

 if α⊨β and ¬α⊨γ, then γ∘Ψβ⇒β⪯∘Ψ∘αγ (D12)

By (D12), if in the state the agent prefers removing a consequence of minimally more than removing a consequence of , then after a decrement of , she is more willing to remove the consequence of .

 Bel(Ψ∘α)⊆Bel(Ψ) (D13)

(D13) axiomatically enforces that a single step does not add any beliefs.

We call operators that fulfil these postulates decrement operators.

Definition 5 (Decrement Operator)

A weak decrement operator is called a decrement operator if satisfies (D8) – (D13).

On the semantic side, we define a specific form of strong faithful assignment which implements decrementing on total preorders.

Definition 6 (Decreasing Assignment)

Let be a hesitant belief change operator. A strong faithful assignment with respect to is said to be a decreasing assignment (with respect to ) if the following postulates are satisfied:

 if ω1,ω2∈\llbracketα\rrbracket%,thenω1≤Ψω2⇔ω1≤Ψ∘αω2 (DR8) if ω1,ω2∈\llbracket¬α\rrbracket, then ω1≤Ψω2⇔ω1≤Ψ∘αω2 (DR9) if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω1≤Ψω2⇒ω1≤Ψ∘αω2 (DR10) if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω1<Ψω2⇒ω1<Ψ∘αω2 (DR11) if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω2≪Ψω1⇒ω1≤Ψ∘αω2 (DR12) if ω1∈\llbracket¬α\rrbracket, ω2∈\llbracketα\rrbracket and ω2≤Ψω3 for all ω3, then ω2≤Ψ∘αω1 (DR13)

The postulates (DR8) to (DR11) are the same as given by Konieczny and Pino Pérez [13] for iterated contraction (cf. Proposition 2). The postulate (DR12) states that a world of which is minimally less plausible than a world of should be made at least as plausible as this world of . (DR13) ensures that (together with the other postulates) that world in stays plausible after a decrement.

The main result is that decrement operators are exactly those which are compatible with a decreasing assignment.

Theorem 4.1 (Representation Theorem for Decrement Operators)

Let be a belief change operator. Then the following items are equivalent:

1. is a decrement operator

2. there exists a decreasing assignment with respect to that satisfies (decrement success), i.e.:

 there exists n∈N0 such that \llbracketΨ∘nα\rrbracket=\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ) and n is the smallest integer such that \llbracketΨ∘nα\rrbracket⊈\llbracketα\rrbracket

The following proposition presents a nice property of decrement operators: Like AGM contraction for epistemic sates (cf. Proposition 1) a decrement operators keeps plausible worlds; and only the least unplausible counter-worlds may become plausible.

Proposition 5

Let be a hesitant belief change operator. If there exists a decreasing assignment with respect to , then we have:

 \llbracketΨ\rrbracket⊆\llbracketΨ∘α\rrbracket⊆\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ) (partial success)

5 Specific Decrement Operators

Unlike improvement operators [12], there is no unique decrement operator. The reason for this is, that if for and , and it is not required otherwise by (DR12), then the relative plausibility of and might not be changed by a decrement operator , i.e. Example 2 demonstrates this.

Example 2

Let and be an epistemic state as given in Table 1. Then the change from to in Table 1 is a valid change by a decrement operator. Likewise, the change from to from Table 1 is also a valid change for a decrement operator.

We capture this observation by two types of decrement operators. In the first case, the decrement operator improves the plausibility of a counter-model whenever it is possible.

Definition 7 (Type-1 Decrement Operator)

A decrement operator is a type-1 decrement operator if there exists a decreasing assignment with:

 if ω1∈\llbracket¬α\rrbracket and% ω2∈\llbracketα\rrbracket, then ω2≃Ψω1⇒ω1≪Ψ∘αω2 (DR14)

The second type of decrement operators keeps the order whenever possible. We capture the cases when this is possible by the following notion. If is a total preorder on worlds, we say is frontal with respect to , if (1.) there is no such that , and (2.) there is no such that . We define the second type of decrement operators as follows.

Definition 8 (Type-2 Decrement Operator)

A decrement operator is a type-2 decrement operator if there exists a decreasing assignment with:

 if ω1∈\llbracket¬α\rrbracket, ω2∈\llbracketα\rrbracket and ω1 is frontal w.r.t α, then% ω2≃Ψω1⇒ω2≃Ψ∘αω1 (DR15)

Indeed, one can show that by the additional constraints the type-1 decrement operators and the type-2 decrement operators are both unique.

Example (continuation of Example 2). The change from to in Table 1 can be made by a type-1 decrement operator, but not by a type-2 decrement operator. Conversely, the change from to from Table 1 can be made by a type-2 decrement operator, but not by a type-1 decrement operator

6 Discussion and Future Work

We provide postulates and representation theorems for gradual variants of AGM contractions in the Darwich-Pearl framework of epistemic states. These so-called weak decrement operators are a generalisation of AGM contraction for epistemic states. Additionally, we give postulates for intended iterative behaviour of these operators, forming the class of decrement operators. For both classes of operators we presented a representation theorem in the framework of total preorders. This fills a gap in the area of non-prioritized belief change.

For future work, we want to investigate the interrelation between (weak) decrement operators and (weak) improvement operators. One approach is to generalize the Levi identity [14] and Haper identity [9] to these operators. Another approach could be the direct definition of a contraction operator from improvement operators, as suggested by Konieczny and Pino Pérez [12]. For such operators, after achieving success, a next improvement may make certain models unplausible, while a decrement operator keeps the plausibility. While this already indicated a difference between the operators, the study of their specific interrelationship is part of future work. Another goal for future work is to generalize (weak) decrement operators to a more general class of gradual change operators [15]. Such operators are candidates for a formalisation of psychologically inspired forgetting operations. An immediate target towards this goal is to take a closer look at subclasses and interrelate them with the taxonomy of improvement operators [11].

Acknowledgements: We would like to thank Gabriele Kern-Isberner for fruitful discussions and her encouragement to follow the line of research leading to this paper. This work was supported by DFG Grant BE 1700/9-1 given to Christoph Beierle as part of the priority program "Intentional Forgetting in Organizations" (SPP 1921). Kai Sauerwald is supported by this Grant.

References

• [1] Carlos E. Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. J. Symb. Log., 50(2):510–530, 1985.
• [2] Christoph Beierle, Gabriele Kern-Isberner, Kai Sauerwald, Tanja Bock, and Marco Ragni. Towards a general framework for kinds of forgetting in common-sense belief management. KI – Künstliche Intelligenz, 33(1):57–68, 2019.
• [3] Richard Booth, Eduardo L. Fermé, Sébastien Konieczny, and Ramón Pino Pérez. Credibility-limited improvement operators. In Torsten Schaub, Gerhard Friedrich, and Barry O’Sullivan, editors, ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic, volume 263 of Frontiers in Artificial Intelligence and Applications, pages 123–128. IOS Press, 2014.
• [4] Thomas Caridroit, Sébastien Konieczny, and Pierre Marquis. Contraction in propositional logic. In Sébastien Destercke and Thierry Denoeux, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 13th European Conference, ECSQARU 2015, Compiègne, France, July 15-17, 2015. Proceedings, volume 9161 of Lecture Notes in Computer Science, pages 186–196. Springer, 2015.
• [5] Thomas Caridroit, Sébastien Konieczny, and Pierre Marquis. Contraction in propositional logic. Int. J. Approx. Reasoning, 80:428–442, 2017.
• [6] Samir Chopra, Aditya Ghose, Thomas Andreas Meyer, and Ka-Shu Wong. Iterated belief change and the recovery axiom. J. Philosophical Logic, 37(5):501–520, 2008.
• [7] A. Darwiche and J. Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1–29, 1997.
• [8] Thomas Eiter and Gabriele Kern-Isberner. A brief survey on forgetting from a knowledge representation and reasoning perspective. KI – Künstliche Intelligenz, 33(1):9–33, 2019.
• [9] William L. Harper. Rational conceptual change. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, 1976:462–494, 1976.
• [10] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263–294, 1992.
• [11] Sébastien Konieczny, Mattia Medina Grespan, and Ramón Pino Pérez. Taxonomy of improvement operators and the problem of minimal change. In Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010. AAAI Press, 2010.
• [12] Sébastien Konieczny and Ramón Pino Pérez. Improvement operators. In Gerhard Brewka and Jérôme Lang, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 2008, Sydney, Australia, September 16-19, 2008, pages 177–187. AAAI Press, 2008.
• [13] Sébastien Konieczny and Ramón Pino Pérez. On iterated contraction: syntactic characterization, representation theorem and limitations of the Levi identity. In Scalable Uncertainty Management - 11th International Conference, SUM 2017, Granada, Spain, October 4-6, 2017, Proceedings, volume 10564 of Lecture Notes in Artificial Intelligence. Springer, 2017.
• [14] Isaac Levi. Subjunctives, dispositions and chances. Synthese, 34(4):423–455, Apr 1977.
• [15] Kai Sauerwald. Student research abstract: Modelling the dynamics of forgetting and remembering by a system of belief changes. In The 34th ACM/SIGAPP Symposium on Applied Computing (SAC ’19), April 8–12, 2019, Limassol, Cyprus, New York, NY, USA, 2019. ACM.

Appendix A Proofs

This appendix contains full proofs for the two representation theorems and for Proposition 5. These proofs rely on three lemmata which are also proven here.

Lemma 1

Let an operator satisfying (D1) to (D4) and , then:

 \llbracketΨ∙¬ω\rrbracket=\llbracketΨ\rrbracket∪{ω}
Proof

The proof is analogue to a proof by Caridroit et. al [5, Lem 13.].∎

Theorem A.1 (Representation Theorem for Weak Decrement Operators)

Let be a belief change operator. Then the following items are equivalent:

1. is a weak decrement operator

2. there exists a strong faithful assignment with respect to such that:

 there exists n∈N0 such that \llbracketΨ∘nα\rrbracket=\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ) and n is the smallest integer such that \llbracketΨ∘nα\rrbracket⊈\llbracketα\rrbracket (decrement success)
Proof

For the (a) to (b)-direction, is an hesitant contraction operator, and the corresponding operator is defined. We define the total preorder as follows:

 ω1≤Ψω2 iff ω1∈\llbracketΨ∙¬(ω1∨ω2)\rrbracket

We show that is a total preorder:

Totality

Let . By definition , and therefore has at least one model and . By (hesitant success) there is an (and we choose here the smallest) such that . Therefore, either or .

Reflexivity

Follows from totality.

Transitivity

Let such that and . We differentiate by case:

• If are not pairwise distinct, then transitivity is easily fulfilled (since is reflexive).

• Assume that are pairwise distinct and for at least one we have . Then in each case it is easy to see that and thus, by (D1), for all it follows .

• Assume that are pairwise distinct and . Towards a contradiction, assume that . By assumption of we have . By Lemma 1 we have . From (D7) we get and by (D5) we have , a contradiction, since and .

We show that is a strong faithful assignment with respect to .

(SFA1)

Let . Then by (D1) we have . Therefore by definition of we have .

(SFA2)

Let and . Then by (D1) we have . Towards a contradiction assume . Since , by we know that . Thus, by (D2) we have .

(SFA3)

Follows directly from (D5).

We show that (decrement success) is fulfilled. We differentiate by case:

• Case with . Then and by definition of we have , especially .

• Case with . Then by (D1) and (D2) we have , resp. . Then there is an such that , thus, we have . We conclude .

• Case with . Then by (D1) we have . We show that every is an element of the set .

First, by (D4) we have . Then every which is an element of leads to a violation of (D4). Thus, we observe that every is an element of .

Second, towards a contradiction suppose such that . Let , and therefore . By definition we have and . By (D5) we have . Then by (D7) and by Lemma 1 we conclude . This shows .

Suppose is an element of such that . Without loss of generality we can assume ; thus, there exists at least one such that . By definition of we have . Clearly , and thus, . Since , we have . Therefore from (D7) we conclude and thus the contradiction . This completes the proof of .

For the (b) to (a)-direction let be a belief change operator and a strong faithful assignment with respect to such that (decrement success) is fulfilled.

(D3)

For and let be the smallest integer such that . By (decrement success) the existence of guaranteed. For , then and therefore is a hesitant contraction operator.

Since satisfies (D3) the corresponding operator is defined.

(D1)

Follows directly by (decrement success).

(D2)

Suppose . Then, is non-empty and by (SFA1) and (SFA2) we have .

(D4)

Let and therefore . Then if and only if . By (decrement success) we conclude . Clearly, .

(D5)

Follows by (SFA3).

(D6)

By (decrement success) we have and we have . Furthermore, it holds that and therefore, we have:

 \llbracketΨ∘(α∧β)\rrbracket⊆\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ)∪min(\llbracket¬β\rrbracket,≤Ψ)=\llbracketΨ∘α\rrbracket∪\llbracketΨ∘β\rrbracket
(D7)

Assume . Then by (decrement success) and (SFA3) we have . This implies that . By basic set theory we get . By (decrement success) this is equivalent to

In summary, the operator is an weak decrement operator. ∎

Lemma 2

Let be a belief change operator. If there exists a strong faithful assignment with respect to which satisfies (DR8), (DR9) and (DR11), then for every and we have:

 \llbracketΨ∘α\rrbracket⊆\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ)
Proof

Let . If we are done, so it remains to show that in the case of .

We first show that if , then . Towards a contradiction suppose this is not the case, i.e. and . Then there a two cases: 1. There exists such that . We easy conclude that and thus, by (DR8), we have . Due to the faithfulness of the assignment , which is a contradiction. 2. For all we have . Then, by using , for all we must have . Thus, and from (DR11) we get . Again, due to the faithfulness of the assignment, we have , which is a contradiction. So every is an element of .

Now we show that every is an element of . Towards a contradiction suppose . Then there exists such that . By (DR9) we can conclude that , which is a contradiction to the assumed faithfulness of the assignment. ∎

Proposition 6

Let be a hesitant belief change operator. If there exists an decreasing assignment with respect to , then we have:

 \llbracketΨ\rrbracket⊆\llbracketΨ∘α\rrbracket⊆\llbracketΨ\rrbracket∪min(\llbracket¬α\rrbracket,≤Ψ) (partial success)
Proof

This is a direct consequence of Lemma 2 and (DR13).∎

Lemma 3

Let be a belief change operator, a strong faithful assignment with respect to and . Then if and only if for each and we have either or .

Proof

The "only if" direction. By definition of we have

 min(\llbracket¬γ\rrbracket,≤Ψ)⊆min(\llbracket¬γ∨¬β\rrbracket,≤Ψ),

which implies . Clearly, it follows that . In the case of we are done.

For the remaining case of suppose there exists such that . This implies that and . Thus, by definition we have . Similarly, we have , since and . Note that this implies . From the previous observations we conclude , and therefore . This leads to , which is a contradiction to . In summary it must be the case that either or .

For the "if" direction suppose that . This implies that and . Thus we have for every and some . Additionally, we have and . Thus we have for every and some . Note that is a total preorder, and thus, we have , a contradiction to the assumptions of or . ∎

Theorem A.2 (Representation Theorem for Decrement Operators)

Let be a belief change operator. Then the following items are equivalent:

1. is a decrement operator

2. there exists a decreasing assignment


text:
Details

# Investigations of the miscibility, crystallization, melting, and deformation behavior of poly(ether ether ketone)/poly(ether imide) blends

Abstract (Summary)
This dissertation reports the studies of the blends of poly(ether ether ketone) (PEEK) and poly(ether imide) (PEI). The investigations reported encompass both the thermodynamic and kinetic aspects of this binary blend. The phase behavior of PEEK/PEI blends in the amorphous states was investigated by differential scanning calorimetry (DSC), density measurement, and Fourier-Transform Infrared (FTIR) spectroscopy. Amorphous PEEK/PEI blends were miscible over the whole composition range. The specific volume measurement and the equilibrium melting point depression analysis showed the existence of favorable interaction between PEEK and PEI. The FTIR study suggested that the oxygen lone-pair electrons of the ether groups in PEEK interact favorably with the electron-deficient imide rings in PEI. The coplanarity of the two nearest imide rings in PEI was changed by blending to accommodate the favorable interaction with PEEK. The two-stage crystallization behavior of PEEK and PEEK/PEI blends was studied by thermal mechanical analysis (TMA) and DSC. The two crystallization stages of PEEK were first time distinguished clearly by measuring the thickness change of PEEK films during isothermal crystallization. A crystallization kinetics model considering both primary and secondary crystallization was applied to extract the respective rate constants of the two crystallization stages. The results were discussed in terms of the diffusion mechanisms during PEEK crystallization. The growth of PEEK spherulites from the pure melt and from the blends with PEI was studied by hot stage optical microscopy. The spherulite growth kinetics was analyzed using a modified Lauritzen-Hoffman theory which considers the diluent effect of PEI. The regime III-II transition was observed for PEEK and PEEK/PEI blends. The side surface free energy, fold surface free energy, and the work of chain folding were calculated, and were discussed in terms of the stiffness and bulkiness of PEEK molecules. The semicrystalline morphology and the melting behavior of PEEK/PEI blends were studied by optical microscopy and DSC, respectively. The optical micrographs of PEEK spherulites grown from the blends showed that a significant amount of PEI was rejected to the interfibrillar regions of the PEEK spherulites. The melting study indicated that PEEK crystal reorganization on heating was hindered by blending with PEI, and this was attributed to the incorporation of PEI in the PEEK crystalline interlamellar regions. The amorphous and the crystalline PEEK/PEI blend films were drawn uniaxially by solid-state coextrusion. The glass transition, density, crystallization behavior, and the respective orientations were studied. The T$\sb{\rm g}$s of amorphous PEEK/PEI blends were depressed by drawing. The kinetics of crystallization of drawn PEEK/PEI blends was also reported. The orientation studies by IR dichroism showed that the orientations of both PEEK and PEI were decreased by increasing PEI content in the blends.
Bibliographical Information:


text:
# Does the typical vector space of polynomials up to a certain degree need to have the constant vectors

I helped a classmate with an exercise about sets of vectors spanning (or not) certain vector spaces. The question was as follows: Does the set $$\{ t, t+t^2, t^3-3t^4, 2t-t^2, -4t^4-t^3 \}$$ span the space $$P_4$$ where this vector space was the polynomials with degree $\leq 4$. (where $t \in \mathbb{R}$)

(this vector space is defined the way it usually is, with coordinates of a vector corresponding with the coefficients of a polynomial)

I said yes because when you write the vectors as a $5$ by $4$ matrix you can use gaussian elimination to end up with 4 monomial vectors (by that I mean the vectors $(1,0,0,0)$ and so on which you would then use as the coefficients of a polynomial). This answer was wrong because the set does not include a constant vector.

Which brings to me to my actual question as to why specifically this is. As far as I have tried you could talk about a vector space of polynomials with degree $\leq k$ and no constant part just fine. I have tried finding where the vector space axioms don't work but I can't seem to find an error.

So is there something I am overlooking where a vector space of polynomials without a constant part would not work? I understand it would be pretty strange since if you're talking about polynomials there is no reason to disregard constant polynomials, especially since they don't cause any problems here, but let's disregard that for a moment.

P.S. yes I corrected my mistake to the classmate

• It's probably better to say "no nonzero constant part", to make sure you are explicitly including the zero polynomial. Jun 17 '18 at 22:51

If I understand you correctly, you are asking two separate questions:

1. Does the set of polynomials of degree $\le n$ have to include constant polynomials?
2. Is the set of polynomials of degree $\le n$ with constant term $=0$ a vector space?

The answer to the first question is Yes; by definition "polynomials of degree $\le n$" includes polynomials of degree $0$, which means that the set of polynmials of degree $\le n$ must include constants.

However, I think you know that already, and I think what you really want to know is the answer to the second question, which is also Yes. One can certainly consider the set of polynomials of degree $\le n$ whose constant terms are $0$, and verify (as you seem to have done) that it satisfies all of the requirements for a vector space. This subspace of $P_n$ can also be described as the subset of $P_n$ consisting of polynomials for which $x$ is a factor.

To bring this back to the question that started the whole thing: the exercise that prompted this asked "Does this set of polynomials span $P_4$?" The answer to that question is no, because $P_4$ contains constant polynomials, and there is no way to get a constant polynomial as a linear combination of the given set of polynomials. It is true that the set of polynomials does span a vector space -- but that vector space is not all of $P_4$. In fact, you can be sure it is not, because (as you have already determined) the vector space spanned by those vectors is 4-dimensional, while $P_4$ is 5-dimensional.

• I would add to your answer that the given problem is about question 1, not question 2, which is why the OP's answer was wrong. Jun 17 '18 at 22:57
• @zipirovich Yes, very good point. I will edit my answer to include that. Jun 17 '18 at 22:59
• Yes that is exactly what I asked, thanks! Jun 17 '18 at 23:28