# BLIP-Diffusion: Pre-trained Subject Representation for Controllable Text-to-
Image Generation and Editing

Dongxu Li†, Junnan Li†, Steven C.H. Hoi†
Salesforce AI Research
†Corresponding authors<EMAIL_ADDRESS>
https://github.com/salesforce/LAVIS/tree/main/projects/blip-diffusion

###### Abstract

Subject-driven text-to-image generation models create novel renditions of an
input subject based on text prompts. Existing models suffer from lengthy fine-
tuning and difficulties preserving the subject fidelity. To overcome these
limitations, we introduce BLIP-Diffusion, a new subject-driven image
generation model that supports multimodal control which consumes inputs of
subject images and text prompts. Unlike other subject-driven generation
models, BLIP-Diffusion introduces a new multimodal encoder which is pre-
trained to provide subject representation. We first pre-train the multimodal
encoder following BLIP-2 to produce visual representation aligned with the
text. Then we design a subject representation learning task which enables a
diffusion model to leverage such visual representation and generates new
subject renditions. Compared with previous methods such as DreamBooth, our
model enables zero-shot subject-driven generation, and efficient fine-tuning
for customized subject with up to 20x speedup. We also demonstrate that BLIP-
Diffusion can be flexibly combined with existing techniques such as ControlNet
and prompt-to-prompt to enable novel subject-driven generation and editing
applications. Implementations will be made public.

Figure 1:  Leveraging the pre-trained subject representation, BLIP-Diffusion
enables subject-driven generation under efficient fine-tuning or zero-shot
setups. The model can also serve as a foundation subject-driven text-to-image
generation model and supports applications such as controlled generation and
image editing, when combined with techniques such as ControlNet [1] and
prompt-to-prompt [2].

##  1 Introduction

Text-to-image generation models have developed significantly and enabled
creation of high-quality images based on textual prompts [3, 4, 5, 6, 7]. One
of their applications is subject-driven generation, which aims to render novel
renditions of an input subject while preserving its appearance. The common
approach to subject-driven generation [8, 9, 10, 11] is through inverting
subject visuals into text embedding space. Specifically, with a pretrained
text-to-image generation model, a placeholder text embedding is optimized to
reconstruct a set of subject images. The embedding is then composed into
natural language prompts to create different subject renditions. One known
inefficiency of this approach is that it requires reiterating hundreds [9, 10]
or thousands [8] tedious fine-tuning steps for each new subject, which hinders
it from efficiently scaling to a wide range of subjects.

We attribute such inefficiency to the fact that most pre-trained text-to-image
models do not natively support multimodal control - using both images and
texts as control input. As a result, it becomes challenging to learn subject
representation that aligns with the text space while capturing the subject
visuals with high fidelity. To overcome these limitations, we introduce BLIP-
Diffusion, the first subject-driven text-to-image generation model with _pre-
trained generic subject representation_ , which enables subject-driven
generation in zero-shot or with few-step fine-tuning. Our model builds upon a
vision-language encoder (_i.e._ BLIP-2 [12]) and a latent diffusion model [6]
(_i.e._ Stable Diffusion). The BLIP-2 encoder takes as input the subject image
and its category text; it produces text-aligned subject representation as
output. We then infix the subject representation in the prompt embedding to
guide the latent diffusion model for subject-driven image generation and
editing.

To enable controllable and high-fidelity generation, we propose a new two-
stage pre-training strategy to learn generic subject representation. In the
first pre-training stage, we perform multimodal representation learning, which
enforces BLIP-2 to produce text-aligned visual features based on the input
image. In the second pre-training stage, we design a subject representation
learning task where the diffusion model learns to generate novel subject
renditions based on the input visual features. To achieve this, we curate
pairs of input-target images with the same subject appearing in different
contexts. Specifically, we synthesize input images by composing the subject
with a random background. During pre-training, we feed the synthetic input
image and the subject class label through BLIP-2 to obtain the multimodal
embeddings as subject representation. The subject representation is then
combined with a text prompt to guide the generation of the target image.

Benefiting from the pre-trained subject representation, BLIP-Diffusion
achieves promising zero-shot subject-driven generation results and superior
fine-tuning efficiency. For example, BLIP-Diffusion takes 40-120 fine-tuning
steps to specialize for a given subject, achieving up to 20x speedup compared
to DreamBooth [9]. Furthermore, BLIP-Diffusion inherits behaviours of the
constituent latent diffusion model and can be flexibly extended to support
various subject-driven generative applications without further training.
Following the prompt-to-prompt [2] approach, BLIP-Diffusion enables editing
images with subject-specific visuals. When combined with ControlNet [1], it
enables subject-driven generation with various additional structure control.

##  2 Related Work

###  2.1 Diffusion Models for Text-to-Image Generation

Diffusion models [3, 4, 6, 7, 13, 14, 15] generate images by progressively
denoising a random variable drawn from a Gaussian distribution. In this work,
we are particularly interested in the pre-trained text-to-image latent
diffusion models [6]. Given a latent variable $z$ and its noisy version
$z_{t}$ obtained by gradually adding noises to $z$ for $t$ steps, latent
diffusion models optimize the following objective:

$\mathbb{E}_{z,c,\epsilon\sim\mathcal{N}(0,1),t}\Bigl{[}\|\epsilon-\epsilon_{\theta}(z_{t},t)\|^{2}_{2}\Bigr{]},$
(1)

which is the squared error between the added noise $\epsilon$ and the
predicted noise $\epsilon_{\theta}(z_{t},t)$ by a neural model
$\epsilon_{\theta}$ at time step $t$, given $c$ a text prompt as condition.
During training, the latent variable $z$ is obtained by passing the image into
a pre-trained encoder [16]. For inference, a decoder is employed to convert
the denoised latent into an image. In addition to text prompts, our model also
conditions on subject representation, rendering an image generation
architecture with multimodal conditions.

###  2.2 Subject-driven Text-to-Image Generation

Given a few images of a subject, the task of subject-driven text-to-image
generation aims at generating the subject in novel context based on text
prompts. In the era of diffusion models, Textual Inversion [8] proposes to
represent visual concepts using a placeholder text embedding, and optimize the
embedding to reconstruct the subject images. DreamBooth [9] shares a similar
methodology while additionally fine-tunes the diffusion model, which leads to
better expressiveness and subject fidelity. One known drawback for both
methods is their lengthy fine-tuning time for each new subject, which prevents
the approaches from easily scaling up. More recent efforts attempt to reduce
the required time and effort for fine-tuning. Concurrent to our effort, the
work [11, 17, 18] pre-train the diffusion model on domain-specific images,
such as cat and human face images. These models provide class-specific prior
for generation thus being more efficient for fine-tuning. However, they are
also constrained to a narrow list of subject categories and are not able to
easily generalize to generic subjects. The work SuTI [19] proposes a knowledge
distillation approach, which learns zero-shot generation from millions of
fine-tuned expert models. Their model shows less flexibility in subject poses
and is likely to be distracted by the background of the input images. In
contrast, the pre-trained representation in our model is generic to a wide
range of subjects, while generalizing efficiently to different subjects.

Figure 2:  Illustration of the two-staged pre-training for BLIP-Diffusion.
Left: in the multimodal representation learning stage, we follow prior work
[12] and pretrain BLIP-2 encoder to obtain text-aligned image representation.
Right: in the subject representation learning stage, we synthesize input
images by composing subjects with random background. The BLIP-2 is then tasked
to produce subject prompt embedding, which is later used by the latent
diffusion model to generate output subject image. The image encoder remains
frozen during pre-training.

##  3 Method

We propose BLIP-Diffusion, the first image diffusion model that features
multimodal control through built-in generic pre-trained subject
representation. Specifically, we adapt BLIP-2 encoder to extract multimodal
subject representation, which is later used together with text prompt to guide
generation.

We aim to learn subject representation that captures the subject-specific
visual appearances while in the meantime aligns well with the text prompt. To
this end, we propose a two-staged pre-training strategy as shown in Figure 2.
First, a multimodal representation learning stage produces text-aligned
generic image representation. Second, a subject representation learning stage
prompts the diffusion model with text and subject representation for subject-
driven generation. In this section, we delineate the model design and pre-
training strategies.

###  3.1 Multimodal Representation Learning with BLIP-2

We use Stable Diffusion [6] as the latent diffusion model, which relies on
CLIP [20] text encoder to produce prompt embeddings. In order to guide the
generation using both text and subject representation as prompt, it is
important that the subject embedding and the text embedding are well-aligned
to ensure they can cooperate with each other. Inspired by the recent vision-
language pre-trained model BLIP-2 [12], which produces high-quality text-
aligned visual representation, we decide to adapt it to extract text-aligned
subject representation.

Specifically, as shown in Figure 2a, we employ two main modules from BLIP-2 to
learn multimodal representation: a frozen pre-trained image encoder to extract
generic image features, and a multimodal encoder (_i.e._ Q-Former) for image-
text alignment. The multimodal encoder is a transformer that accepts a fixed
number of learnable query tokens and an input text. The query tokens interact
with text through self-attention layers, and interact with frozen image
features through cross-attention layers, and produces text-aligned image
features as output. The output is of the same dimension as the number of query
tokens. Empirically, we find that the originally implemented 32 output
features often overpower the CLIP text embeddings when used in combination for
image generation. Therefore, we instead half the number of query tokens and
output 16 features.

Following BLIP-2 pre-training, we jointly train three vision-language pre-
training objectives, including an image-text contrastive learning (ITC) loss
that aligns the text and image representation by maximizing their mutual
information, an image-grounded text generation (ITG) loss that generates texts
for input images, and an image-text matching (ITM) loss that captures fine-
grained image-text alignment via a binary prediction. We conduct multimodal
representation learning on generic image-text paired data, which allows the
model to learn a diverse set of visual and textual concepts.

###  3.2 Subject Representation Learning with Stable Diffusion

As the result of the multimodal representation learning, we obtain text-
aligned visual representation of the input image. These features capture the
generic semantic information of the input image. However, they are not
specifically tailored to serve as guidance for the diffusion model. To this
end, the subject representation learning stage aims to enable the diffusion
model to leverage such visual representation, and generate different
renditions of the subjects when combining with text prompts. In particular, we
consider two desired properties when injecting the subject representation into
a diffusion model. First, we expect the subject representation to well
coordinate with the text prompts for the purpose of text-guided subject-driven
generation. In this regard, prior methods [9, 18, 19] do not address the text
prompts during training. They are thus not directly suitable to be used for
scalable pre-training. Second, the behavior of the underlying diffusion model
should ideally be maintained. This allows the subject-driven generation model
to take advantage of techniques built on top of the original model on the fly,
such as image editing and structure-controlled generation.

Model Architecture. The proposed model architecture is shown in Figure 2b. We
connect the output of the BLIP-2 multimodal encoder to the input of the
diffusion model’s text encoder. During pre-training, the multimodal encoder
takes as input a subject image and a text of the subject category, and
produces a category-aware subject visual representation. We then transform the
subject representation using a feed-forward layer consisting of two linear
layers with GELU [21] activation in-between. The projected features are
appended to the text prompt token embeddings as a soft visual subject prompt.
Specifically, when combining the text token and subject embeddings, we use the
template “[text prompt], the [subject text] is [subject prompt]". Finally, the
combined text and subject embeddings are passed through the CLIP text encoder,
serving as guidance for the diffusion model to generate the output image. The
soft visual prompt makes minimal architectural change to the underlying
diffusion model, rendering an effective solution to inject subject
representation while in the meantime largely inherits the modeling
capabilities of the underlying diffusion model.

Figure 3: Left: example training image pairs, target images (top) and input
images (bottom) with random background. Images are from the OpenImage dataset
[22]. Right: comparison between the subject-driven image generation of our
model (top), and image variations from DALLE-2 [4] (bottom). We prompt our
model with the text prompt “a dog" and the subject representation, while
feeding the input image into DALLE-2 for variation generation. Our model
learns subject representation with minimal background information encoded,
which enables faithful and flexible control when used together with text
prompts.

Subject-generic Pre-training with Prompted Context Generation. We aim to pre-
train the model such that it learns to represent generic subjects from the
input image. To this end, a naive approach is to use the same image as both
input to the multimodal encoder and output to the diffusion model as in [8,
9]. However, our preliminary experiments suggest that this leads to trivial
solutions where generations are significantly interfered by the background in
the inputs, or even models copying the input image as output, rendering
generations not respecting the text prompts. On the other hand, while it is
possible to collect multiple images of the same subject in different context,
and thereby using different images as input and target, such an approach is
laborious to scale up to generic subjects.

To address these issues, we propose a new pre-training task for learning
subject-generic representation, called _prompted context generation_ , where
we curate input-target training pairs by synthesizing images of the subject in
random background. The model takes the synthesized subject image as input, and
aims to generate the original subject image as output according to a text
prompt. Specifically, given an image containing a subject, we first feed the
image and a category text of the subject to a text-prompted segmentation model
CLIPSeg [23] with confidence thresholding. We then build a trimap by taking
the segmentation map with higher confidence as the known foreground, the lower
confidence as the uncertain region and the rest as the known background. Given
the trimap, we use closed-form matting [24, 25] to extract the foreground,
namely the subject. Then we compose the extracted subject onto a random
background image via alpha blending. Finally, we use the synthetic image as
the input and the original subject image as the output to serve as one
training image pair.

As shown in Figure 3, such synthetic pairs effectively separate the foreground
subject and the background context, preventing the subject-irrelevant
information from being encoded in the subject prompt. In this way, we
encourage the diffusion model to consider jointly the subject prompt and the
text prompt for generation, leading to a pre-trained model that can be
faithfully and flexibly controlled by both the subject image and the text
prompt.

During pre-training, we freeze the image encoder and jointly train the BLIP-2
multimodal encoder along with the text encoder and U-Net of the latent
diffusion model. To better preserve the original text-to-image generation
capability, we find it beneficial to randomly drop the subject prompt at a
15$\%$ probability while using only text prompts to guide the diffusion.

Figure 4: Left: BLIP-Diffusion cooperates with ControlNet for structure and
subject controllable generation. Our model maintains the modeling capabilities
of the underlying diffusion model and requires no re-training of the
ControlNet parameters. Right: combined with cross-attention control techniques
present in prompt-to-prompt, our model can be used for subject-driven image
editing. The figure illustrates one denoising step where we mix latent maps
generated with and without subject representation.

###  3.3 Fine-tuning and Controllable Inference

The pre-trained subject representation enables both zero-shot generation and
efficient fine-tuning for specific custom subjects. In addition, our model
provides high-level visual control while inheriting the modeling capabilities
of the underlying diffusion model. This enables us to leverage established
image generation and editing techniques on the fly with BLIP-Diffusion as the
foundation generation model. Below we first describe the efficient few-step
subject-specific fine-tuning for custom subject generation. Then we present
the extension capabilities of BLIP-Diffusion by incorporating existing
techniques including ControlNet [1] and prompt-to-prompt image editing [2].

Subject-specific Fine-tuning and Inference. The pre-trained generic subject
representation enables efficient fine-tuning for highly personalized subjects.
Given a few subject images and the subject category text, we first use the
multimodal encoder to obtain the subject representation individually. We then
initialize the subject prompt embedding using the mean subject representation
of all the subject images. In this way, we cache the subject prompt embedding
without needing a forward pass of the multimodal encoder during fine-tuning.
The diffusion model is fine-tuned to generate subject images as target by
considering the text prompt embedding and the mean subject embedding. We also
freeze the text encoder of the diffusion model, which we find helpful to
counteract overfitting to target images. We use batch size 3 and a constant
learning rate of 5e-5 with AdamW [26] optimizer across all the subjects, and
generally observe decent results after 40-120 training steps, which takes
20-40 seconds to complete on a single A100 GPU.

Figure 5: Qualitative results categorized by generative capabilities.

Structure-controlled Generation with ControlNet. Our model introduces a
multimodal conditioning mechanism for subject-control. In the meanwhile, the
architecture is also compatible to integrate with ControlNet [1] to achieve
simultaneous structure-controlled and subject-controlled generation. Figure 4
illustrates such integration, where we attach the U-Net of the pre-trained
ControlNet to that of BLIP-Diffusion via residuals. In this way, the model
takes into account the input structure condition, such as edge maps and depth
maps, in addition to the subject cues. Since our model inherits the
architecture of the original latent diffusion model, we observe satisfying
generations using off-the-shelf integration with pre-trained ControlNet
without further training.

Subject-driven Editing with Attention Control. Our model combines subject
prompt embeddings with text prompt embeddings for multimodal controlled
generation. Inspired by prompt-to-prompt [2], our model enables subject-driven
image editing by manipulating the cross-attention maps of prompt tokens. In
Figure 4, we show such capability where the model edits the original image
with subject-specific visuals. For this purpose, we assume the generation
process of the original image is known, or can be derived via inversion [13,
27] for real images. To edit the image, we first specify text tokens to edit,
for example the token “dog”. Next, we use the cross-attention maps of the
specified token to extract automatically a mask for regions to edit. In order
to preserve the layout and semantics in unedited regions, we keep the
attention maps from the original generation while generating new attention
maps for the inserted subject embeddings. We mix the denoising latents at each
step based on the extracted editing mask. Namely, latents of the unedited
regions are from the original generation whereas latents of the edited regions
are from the subject-driven generation. In this way, we obtain the edited
image with subject-specific visuals while also preserving the unedited
regions.

##  4 Experiments

###  4.1 Pre-training Datasets and Details.

For multimodal representation learning, we follow BLIP-2 [12] and pretrain the
model on 129M image-text pairs, including 115M image-text pairs from LAION
[28] with CapFilt [29] captions, COCO [30], Visual Genome [31] and Conceptual
Captions [32, 33]. We use ViT-L/14 from CLIP [20] as the image encoder, and
initialize Q-Former with BERTbase [34]. As aforementioned, we use 16 queries
to learn subject representation. Other training hyperparameters follow [29].

For subject representation learning, we use a subset of 292K images from
OpenImage-V6 [22], each containing a salient subject. We also remove images
with human-related subjects. We use BLIP-2 OPT6.7B to generate captions as
text prompts. We obtain a set of 59K background images from the web to
synthesize subject inputs. We use Stable Diffusion v1-5 as the foundation
diffusion model. We use a total batch size 16 with a constant learning rate
2e-6 for 500K steps using AdamW [26] optimizer, taking 6 days to finish on 16
A100 40Gb GPUs. More details on hyperparameters and data filtering procedure
are included in Appendix for reference.

###  4.2 Experimental Results

Figure 6: Qualitative comparison between BLIP-Diffusion with text-driven image
generation methods [8, 9] and the image editing method [35]. Our model
achieves high subject fidelity and prompt relevance, while needing
significantly fewer finetuning steps. Example subject images from the
dreambooth dataset [9] are shown, which are also used as source images for
InstructPix2Pix to edit.

Main Qualitative Results. In Figure 5, we show qualitative generation results
of BLIP-Diffusion. Thanks to the pre-trained subject representation, our model
facilitates zero-shot subject-driven generation (row #1), producing meaningful
results even for highly customized subjects. The model also enables efficient
fine-tuning (row #3-6), demonstrating high-fidelity generation for re-
contextulization, artistic stlyization, textual modification, property
modification and accessorization. Compared with existing solutions, BLIP-
Diffusion requires much less fine-tuning effort, usually 40-120 steps which
are up to x20 times more efficient than previous work [8, 9]. In addition,
when combining with ControlNet (row #7-8), our model can achieve simultaneous
control over structure and subject. Finally, our model can introduce subject
information into image editing pipeline, enable to edit images with specific
subject visuals (row #9-10). These applications demonstrate potentials of
using BLIP-Diffusion as a foundation text-to-image generation model with
multimodal controls.

Comparisons on DreamBooth Dataset. We compare BLIP-Diffusion with methods [8,
9, 35, 36] (details in appendix) on DreamBooth dataset [9], containing 30
subjects, each with 4-7 images. In Figure 6, we show qualitative comparisons.
Our model achieves significantly better subject fidelity than Textual
Inversion, Re-Imagen and InstructPix2Pix. Compared with DreamBooth, our model
exhibits comparable or better generation quality while requiring a significant
lower number of fine-tuning iterations, which validates the effectiveness of
our pre-trained subject representation.

Methods | DINO | CLIP-I | CLIP-T
---|---|---|---
Real Images (Oracle) | 0.774 | 0.885 | -
Textual Inversion [8] | 0.569 | 0.780 | 0.255
Re-Imagen [36] | 0.600 | 0.740 | 0.270
DreamBooth [9] | 0.668 | 0.803 | 0.305
– 100 fine-tuning steps | 0.396 | 0.698 | 0.322
– 300 fine-tuning steps | 0.500 | 0.733 | 0.319
Ours (ZS) | 0.594 ($\pm$0.004) | 0.779 ($\pm$0.003) | 0.300 ($\pm$0.002)
Ours (FT, avg. < 80 steps) |  0.670 ($\pm$0.004) |  0.805 ($\pm$0.002) | 0.302 ($\pm$0.001)

Table 1: Left: Quantitative comparisons on DreamBench. We report average
metrics and differences across 10 experiment runs with different set of random
seeds, in zero-shot (ZS) and fine-tuning (FT) setups. Right: Alignment metrics
in zero-shot (red) and fine-tuning (blue) setups for sample subjects.

In Table 1, we follow [9] and report DINO [37], CLIP-I [20] and CLIP-T scores.
DINO and CLIP-I scores measure subject alignment and CLIP-T measures image-
text alignment (see appendix for detailed description of the metrics). We
generate 4 images for each text prompt, amounting in total 3,000 images for
all the subjects. We repeat generations with 10 fixed set of random seeds and
report average scores. The overall results are consistent with the qualitative
findings, where BLIP-Diffusion is superior to Textual Inversion and Re-Imagen
while showing comparable performance to DreamBooth while requiring less fine-
tuning effort. In particular, our zero-shot generations are better than fine-
tuned Textual Inversion results. Additionally, we show per-subject metrics and
observe that fine-tuning significantly improves subject alignment. In the
meanwhile, fine-tuning also improves image-text alignment on average. When
fine-tuning harms the image-text alignment, it is due to the model overfitting
to target inputs thus resulting in generations irrespective of the text
prompt. This is in particular an issue when the provided subject images are of
limited visual diversity.

Ablation Setups | DINO | CLIP-I | CLIP-T |
---|---|---|---|---
BLIP-Diffusion (250K steps) | 0.566 | 0.773 | 0.299 |
– w/o multimodal pre-training | 0.521 $\downarrow$ | 0.743 $\downarrow$ | 0.290 $\downarrow$ |
– w/o training text encoder | 0.568 $\uparrow$ | 0.782 $\uparrow$ | 0.288 $\downarrow$ |
– w/o subject text | 0.565 $\downarrow$ | 0.772 $\downarrow$ | 0.298 $\downarrow$ |
– w/o subject dropping | 0.559 $\downarrow$ | 0.766 $\downarrow$ | 0.291 $\downarrow$ |

Table 2: Left: Ablation results. Right: Effect of subject representation
learning with varying pre-training steps. Figure 7:  Attention visualization
of subject representation. Leftmost is the generation using prompt “a
robot/car" with subject representation injected. The learned subject
embeddings capture both local (red) and holistic (blue) subject visuals.
Subjects are from the DreamBench [9] dataset.

Ablation Studies. We conduct ablation studies using 250K subject
representation learning steps. Table 2 shows zero-shot evaluation results. Our
findings are: (i) it is critical to conduct multimodal representation learning
(Section 3.1), which bridges the representation gap between subject embeddings
and text prompt embeddings. (ii) freezing text encoder of the diffusion model
worsens the interaction between subject embedding and text embedding. This
leads to generations copying subject inputs and not respecting the text
prompts. Despite leading to higher subject alignment scores, it does not allow
text control, falsifying the task of text-to-image generation. (iii) Giving
subject text to the multimodal encoder is helpful to inject class-specific
visual priors, thereby leading to moderate improvement in metrics. (iv) Pre-
training with random subject embedding dropping helps to better preserve the
diffusion model’s generation ability, thus benefiting the results. We further
demonstrate the effect of subject representation learning. The figure (right)
shows that both image-text alignment and subject alignment improve with
growing pre-training steps of subject representation learning.

Subject Representation Visualization. It is observed that pixels are attracted
more to embeddings that describe them [2]. Following this observation, in
Figure 7, we visualize the learned subject embeddings using cross-attention
maps. The figure shows that the learned embeddings encode fine-grained yet
different aspects of the subject. For example, certain embeddings (_e.g._ 0,
3, 4, 10-13) tend to focus on more local features while others (_e.g._ 1, 14)
encode more holistic visuals. This demonstrates the complimentary effect of
employing multiple subject embeddings.

Zero-shot Subject-driven Image Manipulation. Our model is able to extract
subject features to guide the generation. In addition to applications of
subject-driven generations and editing, we show that such pre-trained subject
representation enables intriguing and useful applications of zero-shot image
manipulation, including subject-driven style transfer and subject
interpolation.

_Subject-driven Style Transfer._ When provided with a subject, the model can
encode the appearance style of it and transfer to other subjects. We refer
such an application as subject-driven style transfer. In Figure 8, we generate
stylized reference subjects with the aid of edge-guided ControlNet. The styles
are hinted by the guiding subjects. Specifically, we feed BLIP-2 with guiding
subjects and their category texts, _e.g._ fire, flower, glass, vase, ball,
bread, to extract the subject representation. In this application, guiding
subjects serve as alternative of textual prompts to specify styles. This is
useful especially when a style is non-trivial to describe by natural languages
accurately.

_Subject Interpolation._ It is also possible to blend two subject
representation to generate subjects with a hybrid appearance. This can be
achieved by traversing the embedding trajectory between subjects. In Figure 9,
we create bilinear interpolations among 4 different subject representations,
and render the interpolated subject in a novel context. As the figure shows,
the subject appearance blends along the trajectory and fits naturally with the
environment. This is useful when multiple subjects are used as reference to
guide the generation. For example, subject interpolation can be used in joint
with subject-driven style transfer to create hybrid style from multiple
guiding subjects.

Figure 8: Zero-shot subject-driven style transfer. On the left we show
reference images and their edge maps; on the right we show by column the
guiding subjects (top) and stylized reference subjects. We use from left to
right “fire", “flower", “glass", “vase", “ball", “vase", “vase", “bread" as
the subject text.  Figure 9: Zero-shot subject interpolation. We interpolate
subject representation and use the same denoising and decoder network for
generation. The intermediate subject representation naturally blends the
subject appearance, while fitting coherently into the new context. We use the
text prompt “A [subject] in the jungle".

##  5 Limitations and Failure Cases

Our model suffers from common failures of subject-driven generation models,
such as incorrect context synthesis, overfitting to training set as detailed
in [9]. In addition, it inherits some weakness of the underlying diffusion
model, which may fail to understand text prompts and fine-grained composition
relations. We show some of such failure examples in Figure10. Despite the
limitations, the proposed technique is generic to harvest future development
of diffusion models.

Figure 10:  Example failure generations. Subject images used for finetuning
are shown on the left.

##  6 Conclusion

This paper proposed BLIP-Diffusion, a new text-to-image diffusion model with
built-in multimodal control capabilities powered by BLIP-2 [12]. The model is
pre-trained using a two-stage strategy to learn progressively multimodal
subject representation, which facilitates high-fidelity zero-shot and
efficient fine-tuned subject-driven generation. BLIP-Diffusion produces better
zero-shot generations than fine-tuned models such as Textual Inversion. It
also achieves up to 20x fine-tuning speed up than best prior methods with
comparable generation quality. In addition, it can work in conjunction with
other established techniques, such as ControlNet and prompt-to-prompt, for
image generation and editing with simultaneous structure and subject control.
We consider BLIP-Diffusion as an important step towards building foundational
text-to-image generation model with multimodal control.

##  Appendix A Appendix

###  A.1 Broader Impact

Image generation models are susceptible to be used as tools for generating
false content or prompting misinformation. Subject-driven generation could be
misused as a tool for generating fake image of individuals. To mitigate this
issue, our model has been trained on generic objects where person-related
subjects have been purposely removed from the training data. This makes the
model weaker at generating fake images using person as subject control.

Our model is built using the pre-trained Stable Diffusion model trained on
web-scraped datasets. Therefore, our model inherits some shortcomings from
Stable Diffusion, such as generating biased contents with social stereotypes,
or other NSFW contents if used inappropriately. Our model’s ability to
precisely control the generation subject can help mitigate certain biases. We
can use NSFW detectors to block potential inappropriate content from being
generated. Nevertheless, we strongly caution against using our model directly
in user-facing applications without a careful inspection of the model’s
output. Proper content moderation and regulation are highly advised to prevent
undesirable consequence.

###  A.2 Competing Methods

We compare BLIP-Diffusion with fine-tuning based [8, 9] and retrieval-
augmented [36] subject-driven generation models on the public DreamBench
dataset [9]. We also compare qualitatively with the image editing method
InstructPix2Pix [35]. We briefly introduce these methods below.

  * •

_Textual Inversion_ [8]: a fine-tuning method which optimizes a placeholder
embedding to reconstruct the training set of subject images. It requires 3,000
training steps for learning a new concept, which takes around 30 minutes on an
A100 GPU.

  * •

_DreamBooth_ [9]: a fine-tuning method similar to textual inversion. In
addition to the placeholder embedding, it also optimizes parameters of the
U-Net for a total budget of around 800 steps. We report intermediate results
using 100 and 300 fine-tuning steps, while refer to metrics reported by the
authors for full model comparison. Fine-tuning DreamBooth on a new concept
costs around 6 minutes on an A100 GPU.

  * •

_Re-Imagen_ : a retrieval-augmented model, which takes the subject images as
references and attend to them to generate new images. While the model requires
no tuning, it significantly underperforms other models. The model is not
publicly available, thus we do not have access to qualitative examples for
comparison.

  * •

_InstructPix2Pix_ : an image editing model, which takes as input the source
image and an editing instruction to generate edited images. Although it does
not represent explicitly subjects, it can be used for applications such as
subject re-contextualization and property modification. Therefore, we also
include it for qualitative comparison. In particular, we experiment with both
low (1.0) and high (1.5) image guidance scales, where a low image guidance
scale preserves less the subject while promotes the text alignment; a high
image guidance scale preserves better the original image yet is more likely to
overlook the editing instruction.

###  A.3 Evaluation Metrics

We adopt metrics proposed in DreamBooth [9] for evaluation, including DINO,
CLIP-I and CLIP-T scores. Among them, DINO and CLIP-I scores are used to
measure subject fidelity and CLIP-T is used to measure image-text alignment.
DINO score is the average pairwise cosine similaity between the ViT-S/16 DINO
embeddings of the generated and real images. CLIP-I score is the average
pairwise CLIP ViT-B/32 image embeddings of the generated and real images. It
is considered that DINO score is the preferred metric for measuring subject
fidelity as it is sensitive to the differences between subjects of the same
class. CLIP-T score is the average cosine similarity between prompt and image
CLIP embeddings.

To better evaluate and compare subject-driven text-to-image models, it is
suggested that these metrics should be considered jointly to avoid biased
conclusion. For example, a model that naively copies the training set images
will produce high DINO and CLIP-I scores with low CLIP-T scores. In the other
case, a vanilla text-to-image generation model without subject knowledge,
_e.g._ stable diffusion, will produce high CLIP-T scores with poor subject
alignment. Both models are not considered desirable for the subject-driven
text-to-image generation task.

###  A.4 Pre-training Datasets

For multimodal representation learning, we use the same pre-training data as
by BLIP-2, totaling 129M images. This includes COCO [30], Visual Genome [31],
CC3M [32], CC12M [33], SBU [38] and 115M images from LAION400M [28]. We also
employ the synthetic captions created using CapFilt method [29] for web
images. We refer interested readers to Section 3.4 in the BLIP-2 paper [12]
for details of the data bootstrapping configurations.

For subject representation learning, we use a subset of OpenImage-V6. We
filter the data using the annotations provided by the dataset. In particular,
we discard a sample if it satisfies one of the following cases: (i) a group of
objects of the same class appear in the image; (ii) the image is taken from
inside of the subject; (iii) the object is of aspect ratios larger than 2;
(iv) objects occupy a too large (0.8) or too small (0.3) area relative to the
image; (v) human-related subject, including boy, girl, person, man, mammal,
woman, human body, human head, human hair, human arm, human face, human leg,
human hand, human foot, human eye, human mouth, human nose, human ear,
clothing, suit; (vi) cluttered objects, including tree, plant, houseplant,
desk, table, poster and billboard. This results in 292K images for subject
representation learning.

###  A.5 Fine-tuning, Inference and Evaluation on DreamBooth Dataset

For all fine-tuning experiments, we use AdamW [26] optimizer with constant
learning rate 5e-6 and no warm-up steps. We use batch size 3, adam beta1 0.9,
adam beta2 0.999, adam epsilon 1e-8 and weight decay 0.01. We fine-tune models
on a single A100 (40Gb) GPU and select checkpoints manually based on a set of
validation prompts. We report the number of iterations for each subject on
DreamBench below, on average 76 steps, taking around 40 seconds to complete on
a single A100.

For inference, we use PNDM scheduler [39] for 100 denoising steps. We use a
fixed guidance scale 7.5 for all experiments.

Table 3: Number of fine-tuning steps for DreamBench subjects. backpack | 110 | backpack-dog | 110 | bear-plushie | 110
---|---|---|---|---|---
bowl | 40 | can | 70 | candle | 80
cat | 40 | cat2 | 50 | clock | 120
colorful-sneaker | 80 | dog | 50 | dog2 | 50
dog3 | 40 | dog5 | 20 | dog6 | 40
dog7 | 50 | dog8 | 40 | duck-toy | 60
fancy-boot | 50 | grey-sloth-plushie | 70 | monster-toy | 120
pink-sunglasses | 90 | poop-emoji | 90 | rc-car | 120
red-cartoon | 70 | robot-toy | 110 | shiny-sneaker | 80
teapot | 120 | vase | 120 | wolf-plushie | 80
Table 4: Average metrics for each subject on DreamBench in zero-shot setup.

Subject | backpack | backpack-dog | bear-plushie | berry-bowl | can | candle
---|---|---|---|---|---|---
DINO | 0.452 | 0.467 | 0.634 | 0.750 | 0.540 | 0.395
CLIP-I | 0.782 | 0.712 | 0.739 | 0.792 | 0.641 | 0.710
CLIP-T | 0.320 | 0.310 | 0.304 | 0.257 | 0.314 | 0.316
Subject | cat | cat2 | clock | colorful-sneaker | dog | dog2
DINO | 0.760 | 0.703 | 0.402 | 0.680 | 0.780 | 0.730
CLIP-I | 0.835 | 0.854 | 0.735 | 0.769 | 0.849 | 0.831
CLIP-T | 0.306 | 0.286 | 0.303 | 0.298 | 0.310 | 0.307
Subject | dog3 | dog5 | dog6 | dog7 | dog8 | duck-toy
DINO | 0.558 | 0.705 | 0.763 | 0.656 | 0.641 | 0.665
CLIP-I | 0.747 | 0.788 | 0.867 | 0.817 | 0.816 | 0.840
CLIP-T | 0.310 | 0.313 | 0.288 | 0.309 | 0.307 | 0.287
Subject | fancy-boot | grey-sloth-plushie | monster-toy | pink-sunglasses | poop-emoji | rc-car
DINO | 0.538 | 0.632 | 0.490 | 0.599 | 0.494 | 0.569
CLIP-I | 0.800 | 0.755 | 0.734 | 0.836 | 0.689 | 0.761
CLIP-T | 0.291 | 0.315 | 0.293 | 0.308 | 0.307 | 0.281
Subject | red-cartoon | robot-toy | shiny-sneaker | teapot | vase | wolf-plushie
DINO | 0.697 | 0.534 | 0.668 | 0.451 | 0.471 | 0.463
CLIP-I | 0.826 | 0.787 | 0.759 | 0.804 | 0.786 | 0.737
CLIP-T | 0.263 | 0.315 | 0.294 | 0.314 | 0.262 | 0.327

Table 5: Average metrics for each subject on DreamBench in fine-tuning setup.

Subject | backpack | backpack-dog | bear-plushie | berry-bowl | can | candle
---|---|---|---|---|---|---
DINO | 0.551 | 0.639 | 0.693 | 0.808 | 0.618 | 0.519
CLIP-I | 0.839 | 0.760 | 0.752 | 0.829 | 0.695 | 0.752
CLIP-T | 0.320 | 0.317 | 0.307 | 0.254 | 0.313 | 0.311
Subject | cat | cat2 | clock | colorful-sneaker | dog | dog2
DINO | 0.806 | 0.747 | 0.479 | 0.739 | 0.821 | 0.793
CLIP-I | 0.869 | 0.864 | 0.784 | 0.805 | 0.860 | 0.841
CLIP-T | 0.306 | 0.284 | 0.305 | 0.320 | 0.313 | 0.307
Subject | dog3 | dog5 | dog6 | dog7 | dog8 | duck-toy
DINO | 0.573 | 0.727 | 0.834 | 0.672 | 0.723 | 0.699
CLIP-I | 0.751 | 0.801 | 0.891 | 0.823 | 0.823 | 0.838
CLIP-T | 0.312 | 0.311 | 0.280 | 0.310 | 0.310 | 0.284
Subject | fancy-boot | grey-sloth-plushie | monster-toy | pink-sunglasses | poop-emoji | rc-car
DINO | 0.649 | 0.717 | 0.566 | 0.625 | 0.627 | 0.651
CLIP-I | 0.827 | 0.780 | 0.743 | 0.826 | 0.784 | 0.775
CLIP-T | 0.299 | 0.322 | 0.292 | 0.312 | 0.290 | 0.288
Subject | red-cartoon | robot-toy | shiny-sneaker | teapot | vase | wolf-plushie
DINO | 0.788 | 0.626 | 0.757 | 0.484 | 0.628 | 0.599
CLIP-I | 0.882 | 0.803 | 0.804 | 0.819 | 0.812 | 0.760
CLIP-T | 0.262 | 0.316 | 0.297 | 0.331 | 0.261 | 0.325

In Table 4 and 5, we report average metrics across 10 experiment runs for each
subject in the dataset, in zero-shot and fine-tuning setups, respectively.

###  A.6 Additional Qualitative Results and Subject Fidelity Showcasing

In Figure 11 to 13, we provide additional qualitative results on DreamBench
subjects and prompts. We show the reference subject image in the first column.
In the rest columns, we provide generated renditions. To showcase subject
fidelity and photorealism, we purposely mix one genuine subject image in and
leave for interested readers to figure out. Read the captions to verify.

Figure 11: Additional qualitative results using DreamBench subjects and
prompts. To showcase subject fidelity and photorealism, we mix one genuine
subject image in the generations for readers to figure out.  Figure 12:
(Cont.) Additional qualitative results using DreamBench subjects and prompts.
To showcase subject fidelity and photorealism, we mix one genuine subject
image in the generations for readers to figure out.  Figure 13: (Cont.)
Additional qualitative results using DreamBench subjects and prompts. To
showcase subject fidelity and photorealism, we mix one genuine subject image
in the generations for readers to figure out.  Figure 14: Zero-shot subject-
driven stylization.  Figure 15: (Cont.) Zero-shot subject-driven stylization.

###  A.7 Additional Zero-shot Subject-driven Style Transfer Results

Our model is able to extract subject features to guide the generation. In
addition to applications of subject-driven generations and editing, we show
that the model also enables _zero-shot_ subject-guided stylization. Namely,
when provided a subject, the model can encode the appearance style of it and
transfer to other subjects. In Figure 14 and 15, we show such applications,
where we generate stylized reference subject in different textures with the
aid of edge-driven ControlNet. In this application, guiding subjects serve as
alternative source of guidance of textual prompts. This is useful especially
when a style is non-trivial to describe by natural languages accurately.

## References

  * [1] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  arXiv preprint arXiv:2302.05543, 2023.
  * [2] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  arXiv preprint arXiv:2208.01626, 2022.
  * [3] Alexander Quinn Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob Mcgrew, Ilya Sutskever, and Mark Chen.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  In International Conference on Machine Learning, pages 16784–16804. PMLR, 2022.
  * [4] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125, 2022.
  * [5] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In International Conference on Machine Learning, pages 8821–8831. PMLR, 2021.
  * [6] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695, 2022.
  * [7] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  arXiv preprint arXiv:2205.11487, 2022.
  * [8] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  arXiv preprint arXiv:2208.01618, 2022.
  * [9] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation.  arXiv preprint arXiv:2208.12242, 2022.
  * [10] Nupur Kumari, Bingliang Zhang, Richard Zhang, Eli Shechtman, and Jun-Yan Zhu.  Multi-concept customization of text-to-image diffusion.  arXiv preprint arXiv:2212.04488, 2022.
  * [11] Rinon Gal, Moab Arar, Yuval Atzmon, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or.  Designing an encoder for fast personalization of text-to-image models.  arXiv preprint arXiv:2302.12228, 2023.
  * [12] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  arXiv preprint arXiv:2301.12597, 2023.
  * [13] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  In International Conference on Learning Representations, 2021.
  * [14] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
  * [15] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8780–8794. Curran Associates, Inc., 2021.
  * [16] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  arXiv preprint arXiv:1312.6114, 2013.
  * [17] Xuhui Jia, Yang Zhao, Kelvin CK Chan, Yandong Li, Han Zhang, Boqing Gong, Tingbo Hou, Huisheng Wang, and Yu-Chuan Su.  Taming encoder for zero fine-tuning image customization with text-to-image diffusion models.  arXiv preprint arXiv:2304.02642, 2023.
  * [18] Jing Shi, Wei Xiong, Zhe Lin, and Hyun Joon Jung.  Instantbooth: Personalized text-to-image generation without test-time finetuning.  arXiv preprint arXiv:2304.03411, 2023.
  * [19] Wenhu Chen, Hexiang Hu, Yandong Li, Nataniel Ruiz, Xuhui Jia, Ming-Wei Chang, and William W Cohen.  Subject-driven text-to-image generation via apprenticeship learning.  arXiv preprint arXiv:2304.00186, 2023.
  * [20] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International conference on machine learning, pages 8748–8763. PMLR, 2021.
  * [21] Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus).  arXiv preprint arXiv:1606.08415, 2016.
  * [22] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, et al.  The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale.  International Journal of Computer Vision, 128(7):1956–1981, 2020\.
  * [23] Timo Lüddecke and Alexander Ecker.  Image segmentation using text and image prompts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7086–7096, 2022.
  * [24] Anat Levin, Dani Lischinski, and Yair Weiss.  A closed-form solution to natural image matting.  IEEE transactions on pattern analysis and machine intelligence, 30(2):228–242, 2007.
  * [25] Thomas Germer, Tobias Uelwer, Stefan Conrad, and Stefan Harmeling.  Pymatting: A python library for alpha matting.  Journal of Open Source Software, 5(54):2481, 2020.
  * [26] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In International Conference on Learning Representations, 2017.
  * [27] Bram Wallace, Akash Gokul, and Nikhil Naik.  Edict: Exact diffusion inversion via coupled transformations.  arXiv preprint arXiv:2211.12446, 2022.
  * [28] Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki.  Laion-400m: Open dataset of clip-filtered 400 million image-text pairs.  arXiv preprint arXiv:2111.02114, 2021.
  * [29] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In International Conference on Machine Learning, pages 12888–12900. PMLR, 2022.
  * [30] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pages 740–755. Springer, 2014.
  * [31] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision, 123:32–73, 2017.
  * [32] Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2556–2565, 2018.
  * [33] Soravit Changpinyo, Piyush Sharma, Nan Ding, and Radu Soricut.  Conceptual 12m: Pushing web-scale image-text pre-training to recognize long-tail visual concepts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3558–3568, 2021.
  * [34] Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of NAACL-HLT, pages 4171–4186, 2019.
  * [35] Tim Brooks, Aleksander Holynski, and Alexei A Efros.  Instructpix2pix: Learning to follow image editing instructions.  arXiv preprint arXiv:2211.09800, 2022.
  * [36] Wenhu Chen, Hexiang Hu, Chitwan Saharia, and William W Cohen.  Re-imagen: Retrieval-augmented text-to-image generator.  arXiv preprint arXiv:2209.14491, 2022.
  * [37] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 9650–9660, 2021.
  * [38] Vicente Ordonez, Girish Kulkarni, and Tamara Berg.  Im2text: Describing images using 1 million captioned photographs.  Advances in neural information processing systems, 24, 2011.
  * [39] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao.  Pseudo numerical methods for diffusion models on manifolds.  In International Conference on Learning Representations, 2022.


# Solutions of the equation
$a_{n}+(a_{n-1}+\cdots(a_{2}+(a_{1}+x^{r_{1}})^{r_{2}}\cdots)^{r_{n}}=b\,x$

Daniel Panazzolo111This material is based upon work supported by the Agence
Nationale de la Recherche under Grant ANR-23-CE40-0028.
Université de Haute-Alsace

###### Abstract

We establish a novel upper bound for the real solutions of the equation
specified in the title, employing a generalized derivation-division algorithm.
As a consequence, we also derive a new set of Chebyshev functions adapted
specifically for this problem.

Dedicated to Jorge Sotomayor

## Introduction

The equation

$a_{n}+(a_{n-1}+\cdots(a_{2}+(a_{1}+x^{r_{1}})^{r_{2}}\cdots)^{r_{n}}=b\,x$
(1)

frequently emerges in problems concerning the qualitative theory of vector
fields. In these problems, the variables $(b,a,r)$, belonging to
$\mathbb{R}_{>0}\times\mathbb{R}^{2n}$, are treated as free parameters. The
goal is to estimate the number of real solutions $x$ to this equation,
uniformly with respect to the parameters.

For instance, consider a smooth planar vector field $X$ whose phase portrait
has a hyperbolic polycycle $\Gamma$ with $n$ saddle points
$s_{1},\ldots,s_{n}$ and let $X_{\lambda}$ be a smooth family of vector fields
which unfolds $X$. We fix a local transverse section $\Sigma$ (see picture
below) such that $\Sigma\cap\Gamma=\\{p\\}$ and consider the first return map
$\pi:(\Sigma,p)\rightarrow(\Sigma,p)$, which depends on the parameter
$\lambda$. The limit cycles bifurcating from $\Gamma$ are related to the
isolated fixed points of $\pi$.

According a result of Mourtada (see [9], Theorem 1), in the vicinity of the
parameter value $\lambda=0$, there exists an appropriate domain on the
transversal where the fixed-point equation $\pi(x)=x$ has an expansion of the
form (1), up to some error term which is innocuous under generic conditions.
Here the parameters $(a,r)$ depend smoothly on $\lambda$ and measure
respectively the distance between the saddle separatrices and the ratio of
eigenvalues at the saddle points. The additional parameter $b>0$ is related to
the first multiplier of the Poincaré map along the unperturbed polycycle and
is only relevant if the product $r_{1}\cdots r_{n}$ equals one.

In such particular setting, one is interested in finding an upper bound for
the cyclicity of the origin. Namely, the number of solutions (1) bifurcating
from $x=0$ under small perturbation of the parameters.

Another situation where (1) appears is related to slow-fast systems. More
specifically, it is shown in [4] that such equation appears in the study of
limit cycles under bifurcation from multi-layer canard cycles. In contrast to
the previous situation, here one is interested in finding a global uniform
bound for the number of isolated solutions.

Independently, the structure of the group $G$ of real functions generated by
translations $x\mapsto x+a$ and power maps $x\mapsto x^{r}$ is a subject of
interest in group theory (see e.g. [2]). Here, one is interested in the
abstract structure of such group and one natural question is whether $G$ is
isomorphic to a free product. From a dynamical systems point of view, this
problem is related to the following question, usually called center problem:
Characterise those hyperbolic polycycles which lie on the boundary of a
continuum of periodic orbits, i.e. those polycycles for which the Poincaré
first return map $\pi$ is the identity. We refer the reader to [11] for some
results on this direction.

In this paper, we will be interested in estimating the maximum number of real
solutions of (1). To state the problem precisely, we need some definitions:
Given $(a,r)\in\mathbb{R}^{2n}$, let $I_{n}(a,r)\subset\mathbb{R}$ denote the
subset of all real numbers $x$ such that the functions $g_{0},\ldots,g_{n}$
defined by

$g_{0}(x)=x\quad\mbox{ and }\quad g_{i+1}(x)=a_{i+1}+g_{i}(x)^{r_{i+1}},\mbox{
for }i=1,\ldots,n-1.$ (2)

are all strictly positive. Since all these functions are strictly monotone
(increasing or decreasing), it is easy to see that $I_{n}(a,r)$ is an open
(possibly empty) interval of $\mathbb{R}$. If the $r_{i}$ are all positive,
$I_{n}(a,r)$ is a nonempty neighborhood of infinity.

######  Remark 0.1.

The set $\\{(a,r,I_{n}(a,r)):(a,r)\in\mathbb{R}^{n}\times\mathbb{R}^{n}\\}$ is
an open subset of $\mathbb{R}^{2n+1}$ which belongs to the o-minimal structure
of sets definable in the expansion of the real field by the Pfaffian functions
(in the sense of Khovanskii).

So, our goal is to estimate the number of connected components of the solution
set

$S_{n}(b,a,r)=\\{x\in I_{n}(a,r)\mid
a_{n}+(a_{n-1}+\cdots(a_{1}+x^{r_{1}})^{r_{2}}\cdots)^{r_{n}}-bx=0\\},$ (3)

Let $\mathrm{FP}_{n}(b,a,r)$ denote the number of such connected components.
It follows immediately from the analyticity of the functions in (2) that for
each fixed parameter $(b,a,r)$, either $S_{n}(b,a,r)\equiv I_{n}(a,r)$ or
$S_{n}(b,a,r)$ is a finite set of points. As a consequence,
$\mathrm{FP}_{n}(b,a,r)<\infty$, and we define

$\mathrm{fp}(n)=\sup_{(b,a,r)}\mathrm{FP}_{n}(b,a,r)$ (4)

The first obvious question is whether $\mathrm{fp}(n)<\infty$. This is a
direct Corollary of Khovanskii’s Fewnomial theory [7]. Indeed, by introducing
auxiliary variables $(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}_{+}$, equation (1)
can be equivalently written as a system,

$\displaystyle a_{1}+x_{1}^{r_{1}}=x_{2}\hfill$ $\displaystyle
a_{2}+x_{2}^{r_{2}}=x_{3}\hfill$ $\displaystyle\vdots$ $\displaystyle
a_{n}+x_{n}^{r_{n}}=b\,x_{1}\hfill$

In such form, we have a system of $n$ equations in $n$-variables with $2n+1$
distinct monomials, and the theory of Khovanskii provides the bound

$\mathrm{fp}(n)\leq\mathrm{K}(n):=2^{n(2n-1)}(n+1)^{2n}$

(see [7]). In [1], Sotille and Bihan slightly improved the fewnomial’s bound.
Their result implies that
$\mathrm{fp}(n)\leq\mathrm{SB}(n):=\frac{e^{2}+3}{4}\,2^{\binom{n}{2}}n^{n}$.

One of the difficulties of the problem is that, in general, the sequence (2)
is not a Chebyshev system (see e.g. [3], Section 3.3, for the definition). To
the author’s knowledge, this was first observed in Mourtada’s thesis [6]. In
that work, Mourtada constructed a specific example of a generic hyperbolic
polycycle with four singularities which bifurcates into five limit cycles. In
our notation, this result translates to $\mathrm{fp}(4)\geq 5$. We shall see
in Section 2 that $\mathrm{fp}(4)\leq 13$ and, in Section 4, that in fact
$\mathrm{fp}(3)=5$. The exact value of $\mathrm{fp}(n)$ is unknown for $n\geq
4$.

In the next Sections, we shall describe a simple algorithm which gives a new
upper bound for $\mathrm{fp}(n)$ by a derivation-division algorithm. The
algorithm is somewhat inspired in [8].

Such new upper bound coincides with the exact value of $\mathrm{fp}(n)$ for
$n\in\\{1,2,3\\}$ and is significantly smaller the Khovanskii’s and Bihan-
Sottile’s bound for $n\leq 5$. However, it is largely outperformed by such
bounds for $n\geq 6$. We refer to Section 6 for a more detailed comparison.

One of the advantages of our method is that it provides as a by-product a
system of linearly independent monomials which allows to expand the left-hand
side of (1) uniformly with respect to the parameters $(a,r)$. This expansion
can be interpreted as a generalization of the compensator-type expansion
introduced independently by Roussarie [12] and Ecalle [5]. We refer to Section
5 for the details.

##  1 Derivation/division for Laurent polynomials

We initially consider a more abstract setting of a certain ring equipped with
a derivation.

Given $n\in\mathbb{N}$, let $R=\mathbb{Z}[R_{1},..,R_{n}]$ denote the
commutative ring of polynomials $n$ variables $R_{1},\ldots,R_{n}$ with
integer coefficients. Our basic object will be the ring

$\mathbb{L}_{n}=R[x_{1}^{\pm},y_{1}^{\pm},\ldots,x_{n}^{\pm},y_{n}^{\pm}],$

i.e. the ring of Laurent polynomials in $x_{i},y_{i}$ with coefficients in
$R$. We will frequently use the fraction notation and write, for instance,
$x_{1}y_{1}^{-1}$ simply as $x_{1}/y_{1}$. We convention that
$\mathbb{L}_{0}=R$.

A monomial in $\mathbb{L}_{n}$ is polynomial of the form
$\mathfrak{m}=c\,x^{k}y^{l}$, with a nonzero coefficient $c\in
R\setminus\\{0\\}$ and where we note

$x^{k}y^{l}:=x_{1}^{k_{1}}\cdots x_{n}^{k_{n}}y_{1}^{l_{1}}\cdots
y_{n}^{l_{n}}$

The vector $(k,l)\in\mathbb{Z}^{n}\times\mathbb{Z}^{n}$ will be called the
exponent $\mathfrak{m}$ and we say $\mathfrak{m}$ unitary if $c=1$. The
(poly)-degree of a such monomial is the integer vector
$\mathrm{pdeg}(\mathfrak{m})=k+l\in\mathbb{Z}^{n}$. We note that all unitary
monomials are invertible element of $\mathbb{L}_{n}$.

Each non-zero polynomial $p\in\mathbb{L}_{n}$ can be written as a finite sum
of monomials

$p=\sum_{i\in I}\mathfrak{m}_{i}$ (5)

where the set $\mathrm{supp}(p)=\\{\mathfrak{m}_{i}:i\in I\\}$ will be called
the support of $p$. We now define successively three subrings of
$\mathbb{L}_{n}$.

$\mathbb{L}_{n}^{\mathrm{reg}}\subset\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]\subset\mathbb{L}_{n}^{\mathrm{hom}}\subset\mathbb{L}_{n}$
(6)

Firstly, we denote by $\mathbb{L}_{n}^{\mathrm{hom}}\subset\mathbb{L}_{n}$ the
subring of Laurent polynomials which are homogeneous, i.e. such that all
monomials in their support have a same degree. We will note by
$\mathrm{pdeg}(p)\in\mathbb{Z}^{n}$ the degree of an element $p$ of
$\mathbb{L}_{n}^{\mathrm{hom}}$. For each $1\leq j\leq n$, we will denote by
$\mathrm{pdeg}_{j}(p)\in\mathbb{Z}$ the degree of $p$ with respect to the
variables $(x_{j},y_{j})$ (i.e. the $j^{th}$-component of $\mathrm{pdeg}(p)$).

We now define
$\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]\subset\mathbb{L}_{n}^{\mathrm{hom}}$
as the subring of homogeneous Laurent polynomials which are polynomials in the
$(x_{n},y_{n})$-variables. In other words, we consider the Laurent polynomials
$p$ such that each monomial $\mathfrak{m}=cx^{k}y^{l}\in\mathrm{supp}(p)$ has
an exponent $(k,l)$ satisfying $k_{n},l_{n}\geq 0$. Thus, if we let
$m=\mathrm{pdeg}_{n}(p)$ and denote the variables $(x_{n},y_{n})$ simply as
$(x,y)$, we can expand such element $p$ in the form

$p=\sum_{j=0}^{m}q_{j}x^{j}y^{m-j}$ (7)

with coefficients $q_{j}$ in $\mathbb{L}_{n-1}^{\mathrm{hom}}$.

Finally, we define the smallest subring
$\mathbb{L}_{n}^{\mathrm{reg}}\subset\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]$
appearing in (6), whose elements will be called $n$-regular polynomials. The
definition is by induction on $n$:

  * (i)

For $n=0$, the 0-regular polynomials are simply $L_{0}^{\mathrm{reg}}=R$.

  * (ii)

For $n\geq 1$, we say that a Laurent polynomial
$p\in\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]$ is $n$-regular if the
coefficient $q_{0}$ in the expansion (7) is $(n-1)$-regular.

Note that, in particular, if $p\in\mathbb{L}_{n}^{\mathrm{reg}}$ then
$\mathrm{pdeg}(p)\in\mathbb{N}^{n}$ is a positive vector and if
$\mathrm{pdeg}_{n}(p)=0$ then $p$ is $(n-1)$-regular. Inductively, we show
that $\mathrm{pdeg}(p)=0$ if and only if $p$ belongs to the base ring $R$.

Let us give a different characterisation of $\mathbb{L}_{n}^{\mathrm{reg}}$.
Consider a homogeneous Laurent polynomial $p\in\mathbb{L}_{n}^{\mathrm{hom}}$
of degree $\mathrm{pdeg}(p)=(m_{1},..,m_{n})\in\mathbb{N}^{n}$. Then $p$ is
$n$-regular if and only if there exists a sequence of nonzero Laurent
polynomials $p_{j}\in\mathbb{L}_{j-1}^{\mathrm{hom}}[x_{j},y_{j}]$ for $0\leq
j\leq n$ such that:

  * (1)

$p_{n}=p$ and

  * (2)

for each $1\leq j\leq n$, $\mathrm{pdeg}_{j}(p_{j})=m_{j}$ and we can
inductively write

$p_{j}=Q_{j}+p_{j-1}y_{j}^{m_{j}}$

where $Q_{j}\in\mathbb{L}_{j-1}^{\mathrm{hom}}[x_{j},y_{j}]$ is divisible by
$x_{j}$ (as a polynomial in $(x_{j},y_{j})$). In other words, $Q_{j}$ contains
only monomials of the form $\star x_{j}^{\alpha}y_{j}^{\beta}$ with positive
exponents $\alpha,\beta$ such that $\alpha+\beta=m_{j}$ and $\beta<m_{j}$.

This result leads to the following nested form for $p$,

$p=Q_{n}+(\cdots(Q_{2}+(Q_{1}+\alpha
y_{1}^{m_{1}})y_{2}^{m_{2}})\cdots)y_{n}^{m_{n}}$ (8)

for some $\alpha\in R$.

######  Example 1.1.

For $n=2$, the Laurent polynomials

$p=\frac{x_{1}}{y_{1}}x_{2}+y_{2}\qquad
q=\left(\frac{x_{1}^{2}}{y_{1}}+\frac{x_{1}^{3}}{y_{1}^{2}}+x_{1}+\frac{y_{1}^{2}}{x_{1}}\right)x_{2}y_{2}+(x_{1}+y_{1})y_{2}^{2}$

are regular, of respective degrees $\mathrm{pdeg}(p)=(0,1)$ and
$\mathrm{pdeg}(q)=(1,2)$

We now turn $\mathbb{L}_{n}$ into a differential ring by introducing a
derivation

$\partial:\mathbb{L}_{n}\rightarrow\mathbb{L}_{n}$

which satisfies $\partial(R)=0$ and acts on the variables $x_{j},y_{j}$
according to the following formulas

$\partial(y_{1})=\partial(x_{1})=\Delta_{1}x_{1},\qquad\partial(y_{j})=\partial(x_{j})=\Delta_{j}x_{j}\,\frac{x_{1}\cdots
x_{j-1}}{y_{1}\cdots y_{j-1}},\qquad j\geq 2$ (9)

where we define $\Delta_{j}=R_{1}\cdots R_{j}\in R$. The following result is
an obvious consequence of the above expressions for $\partial$ and the Leibniz
rule.

######  Proposition 1.2.

(1) The derivation $\partial$ maps the ring
$\mathbb{L}_{j-1}^{\mathrm{hom}}[x_{j},y_{j}]$ into itself, for each index
$1\leq j\leq n$.
(2) Given $p\in\mathbb{L}_{j-1}^{\mathrm{hom}}[x_{j},y_{j}]$, we either have
$\partial p=0$ or else

$\mathrm{pdeg}(\partial p)=\mathrm{pdeg}(p)$

in other words, $\partial$ preserves the degree.

###### Proof.

By linearity, it suffices to consider the case of a monomial
$\mathfrak{m}=x^{k}y^{l}$. Then, from the Leibniz rule, have

$\partial\,\mathfrak{m}=x^{k}y^{l}\sum_{j=1}^{n}k_{j}\frac{\partial(x_{j})}{x_{j}}+l_{i}\frac{\partial(y_{j})}{y_{j}}=x^{k}y^{l}\sum_{j=1}^{n}\Delta_{j}P_{j-1}(k_{j}+l_{j}\frac{x_{j}}{y_{j}})$

where $P_{j-1}=\frac{x_{1}\cdots x_{j-1}}{y_{1}\cdots y_{j-1}}$ and $P_{0}=1$.

We now remark that each term $P_{j-1}$ is a Laurent homogeneous polynomial of
degree $0$. Therefore, by the additivity of the degree under multiplication,
we easily obtain

$\mathrm{pdeg}(\partial\,\mathfrak{m})=\mathrm{pdeg}(\mathfrak{m}).$

Finally, if we further suppose that $m$ belongs to
$\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]$ (i.e. $k_{n},l_{n}\geq 0$) then
it follows from the above formula that $\partial\mathfrak{m}$ is a sum of
monomials lying in $\mathbb{L}_{n-1}^{\mathrm{hom}}[x_{n},y_{n}]$. The same
argument works if $\mathfrak{m}$ lies in
$\mathbb{L}_{j-1}^{\mathrm{hom}}[x_{j},y_{j}]$. ∎

We observe however that the ring $\mathbb{L}_{n}^{\mathrm{reg}}$ is not
preserved by $\partial$, as the following simple example shows:

######  Example 1.3.

Consider the polynomial $p$ given in Example 1.1. Then,

$\partial
p=\left(\Delta_{1}\frac{x_{1}}{y_{1}}+(2\Delta_{2}-\Delta_{1})\frac{x_{1}^{2}}{y_{1}^{2}}\right)x_{2}$

which is not a Laurent regular polynomial according to our definition.

In order to deal with such phenomena, we observe that any element of
$\mathbb{L}^{\mathrm{hom}}_{n}$ can be transformed into a regular Laurent
polynomial upon division by an appropriate monomial.

More precisely, the regularization monomial associated to a non-zero Laurent
polynomial $p\in\mathbb{L}^{\mathrm{hom}}_{n}$ is a unitary monomial
$\mathfrak{m}=x^{k}y^{l}$ inductively defined as follows:

  * (i)

Case $n=0$: We define $\mathfrak{m}=1$.

  * (ii)

Case $n\geq 1$: If we note $m=\mathrm{pdeg}_{n}(p)$ then we observe that we
can write an expansion of $p$ in the variables $(x,y)=(x_{n},y_{n})$ as

$p=\sum_{j=n_{0}}^{n_{1}}q_{j}x^{j}y^{m-j}$

for some (possibly negative) integers $n_{0}\leq n_{1}$ and coefficients
$q_{j}\in\mathbb{L}_{n-1}^{\mathrm{hom}}$ such that $q_{n_{0}},q_{n_{1}}$ are
non-zero. We then define
$\mathfrak{m}=x^{n_{0}}y^{d-n_{1}}\bar{\mathfrak{m}}$, where
$\bar{\mathfrak{m}}$ is the regularization monomial of $q_{n_{0}}$.

We will denote such monomial $\mathrm{reg}(p)=\mathfrak{m}$. The following
result is obvious:

######  Proposition 1.4.

The Laurent polynomial $p/\mathrm{reg}(p)$ is regular.

######  Example 1.5.

Consider the polynomial $q=\partial p$ given in Example 1.3. Then, the above
definitions gives $\mathrm{reg}(q)=\frac{x_{2}}{x_{1}}{y_{1}^{2}}$. The
Laurent polynomial

$r\coloneq\frac{q}{\mathrm{reg}(q)}=\Delta_{1}y_{1}+(2\Delta_{2}-\Delta_{1})x_{1}+\Delta_{1}y_{1}$

is regular, and has degree $\mathrm{pdeg}(r)=(1,0)$.

######  Theorem 1.6.

Suppose that $p\in\mathbb{L}_{n}^{\mathrm{reg}}$. Then either $\partial p=0$
or the regular polynomial

$q=\frac{\partial p}{\mathrm{reg}(\partial p)}$

is such that $\mathrm{pdeg}(q)<_{\mathrm{rlex}}\mathrm{pdeg}(p)$.

######  Remark 1.7.

Here we denote by $<_{\mathrm{rlex}}$ the usual reverse lexicographical
ordering in $\mathbb{N}^{n}$, namely

$(m_{1},..m_{n})<_{\mathrm{rlex}}(m_{1}^{\prime},..,m_{n}^{\prime})\Longleftrightarrow\exists
i:(m_{j}<m_{j}^{\prime},i<j\leq n)\land m_{i}<m_{i}^{\prime}$

###### Proof.

If $\mathrm{pdeg}(p)=0$ then necessarily $p\in R$ and hence $\partial p=0$.
So, let us assume that $\mathrm{pdeg}(p)=(m_{1},\ldots,m_{n})$ is such that
$m_{1}=\cdots=m_{j-1}=0$ and $m_{j}\geqslant 1$, for some $1\leq j\leq n$. We
claim that the polynomial $q$ defined in the enunciate satisfies

$\mathrm{pdeg}(q)\leq_{\mathrm{rlex}}(0,\ldots,0,m_{j}-1,m_{j+1},\ldots,m_{n})$
(10)

Indeed, it follows from the definition of regularity and the assumption on
$\mathrm{pdeg}(p)$ that the expansion (8) can be rewritten as

$p=Q_{n}+(\cdots(Q_{j+1}+(Q_{j}+\alpha
y_{j}^{m_{j}})y^{m_{j+1}}_{j+1})\cdots)y^{m_{n}}_{n}$ (11)

where $\alpha\in R\setminus\\{0\\}$ and, for each index $j\leq i\leq n$, the
coefficient $Q_{i}$ is an element
$\mathbb{L}_{i-1}[x_{i},y_{i}]^{\mathrm{hom}}$ containing only exponents in
$x_{i}^{m_{i}}y_{i}^{0},\ldots,x_{i}y_{i}^{m_{i}-1}$. We recall that the
derivation $\partial$ applied to each monomial $y_{i}^{m_{i}}$ gives

$\partial y_{i}^{m_{i}}=m_{i}\Delta_{i}x_{i}y_{i}^{m_{i}-1}P_{i-1}$

where $P_{i-1}=\frac{x_{1}\cdots x_{i-1}}{y_{1}\ldots
y_{i-1}}\in\mathbb{L}_{i-1}^{\mathrm{hom}}$. In particular, for the innermost
term in the expansion (11), we can write

$\partial(Q_{j}+\alpha y_{j}^{m_{j}})=\partial Q_{j}+\alpha\partial
y_{j}^{m_{j}}=\widetilde{P_{j}}$

where $\tilde{P}_{j}$ is a Laurent polynomial in
$\mathbb{L}_{j-1}[x_{j},y_{j}]^{\mathrm{hom}}$ containing only exponents in
$x_{j}^{m_{j}}y_{j}^{0},\ldots,x_{j}y_{j}^{m_{j}-1}$ (and hence is divisible
by $x_{j}$).

More generally, applying the derivation $\partial$ to the nested expression of
$p$ given above, we obtain

$\partial
p=\tilde{Q}_{n}+(\cdots(\tilde{Q}_{j+1}+\tilde{P}_{j}y^{m_{j+1}}_{j+1})\cdots)y^{m_{n}}_{n}$

where, for each index $j+1\leqslant i\leqslant n$, the coefficient
$\tilde{Q}_{i}$ is a Laurent polynomial in
$\mathbb{L}_{i-1}[x_{i},y_{i}]^{\mathrm{hom}}$ which contains only exponents
in $x_{i}^{m_{i}}y_{i}^{0},\ldots,x_{i}y_{i}^{m_{i}-1}$.

Considering separately the cases $P_{j}=0$ and $\tilde{P}_{j}\neq 0$, it now
suffices to observe that the division of $\partial p$ by its regularization
monomial $\mathrm{reg}(\partial p)$ results into a regular polynomial $q$ such
that (10) holds. ∎

Applying successively the above Theorem, we obtain the following:

######  Corollary 1.8 (Derivation-division Algorithm).

Let $p\in\mathbb{L}_{n}^{\mathrm{reg}}$. Then the sequence $(p^{(n)})_{n\geq
0}$ of Laurent polynomials in $\mathbb{L}_{n}^{\mathrm{reg}}$, defined
inductively as

$p^{(0)}=p,\qquad
p^{(n+1)}=\frac{\partial\,p^{(n)}}{\mathrm{reg}(\partial\,p^{(n)})},\quad
n\geq 0$

eventually gives an element $p^{(n)}\in R$.

###### Proof.

It suffices to observe that if $p\in\mathbb{L}_{n}^{\mathrm{reg}}$ then
$\mathrm{pdeg}(p)\in\mathbb{N}^{n}$ and moreover $p\in R$ if and only if
$\mathrm{pdeg}(p)=0$. ∎

In the above setting, we define the derivation-division complexity of $p$ as
the smallest integer $m=\mathrm{DD}(p)\geq 0$ such that $p^{(m)}\in R$.

######  Remark 1.9.

The basic idea behind the derivation-division algorithm is quite simple: The
expressions given in (9) show that $\partial(y_{j})$ only depends on the
variables $x_{1},\ldots,x_{j}$ and $y_{1},..,y_{j-1}$. Hence, we inductively
eliminate all monomials in $y_{1},..,y_{n}$ and then divide out by the maximal
possible factors in $x_{1},..,x_{n}$.

######  Example 1.10.

Let $n=1$. Writing the variable $(x_{1},y_{1})$ simply as $(x,y)$, a
polynomial $p\in\mathbb{L}^{\mathrm{reg}}$ of degree $m$ has the form

$p=\sum_{j=0}^{m}\alpha_{j}x^{j}y^{m-j}$

where the coefficients $\alpha_{j}$ lie on the ring $R$. Applying the
derivation $\partial$ to each monomial $x^{j}y^{m-j}$ gives

$\partial
x^{j}y^{m-j}=\Delta_{1}\left(jx^{j}y^{m-j}+(m-j)x^{j+1}y^{m-j-1}\right)$

Therefore, we can write $\partial p=\sum_{j=0}^{m}\beta_{j}x^{j}y^{m-j}$ where

$\beta_{j}=\Delta_{1}\left(j\alpha_{j}+(m-j-1)\alpha_{j-1}\right),\quad j\geq
1$

and $\beta_{0}=0$. As a consequence, $\partial p$ is divisible by $x$ and the
polynomial $p^{(1)}=\partial p/x$ has degree at most $m-1$. We conclude by
induction that $\mathrm{DD}(p)\leq m$.

######  Example 1.11.

Let $n=2$. Denoting the variables $(x_{1},y_{1})$ and $(x_{2},y_{2})$ simply
by $(x,y)$ and $(x^{\prime},y^{\prime})$, we consider the special case where
$p\in\mathbb{L}^{\mathrm{reg}}$ is such that

$p\in R[x,x^{\prime},y,y^{\prime}]$

In other words, we assume that our initial Laurent polynomial is indeed an
homogeneous polynomial. Writing $\mathrm{pdeg}(p)=(m^{\prime},m)$, we claim
that in this case $\mathrm{DD}(p)\leq m(m^{\prime}+1)+m^{\prime}$.

If $m=0$, we fall in the situation of the Example 1.10 and the estimate holds.
So, let us suppose that $m\geq 1$ and write the expansion

$p=Q_{1}+p_{0}y^{m}$

where $Q_{1}=\sum_{j=1}^{m}{q_{j}x^{j}y^{m-j}}$ and $p_{0}$ is a an element of
$\mathbb{L}^{\mathrm{reg}}_{1}$. In fact, due to our hypothesis,
$p_{0},q_{1},..,q_{m}$ are all homogeneous polynomials of degree $m^{\prime}$
in variables $(x^{\prime},y^{\prime})$.

After at most $m^{\prime}$ steps of the derivation-division algorithm, we
obtain a new Laurent polynomial of the form

$q=R_{1}+\alpha y^{m},$

of degree $\mathrm{pdeg}(q)=(0,m)$. Here $\alpha\in R$ and we have
$R_{1}=\sum_{j=1}^{m}{r_{j}x^{j}y^{m-j}}$, where each coefficient $q_{j}$ is a
Laurent polynomial with support contained in the set of monomials $x^{\prime
i}y^{\prime-i}$, with $i\in\\{0,..,m\\}$. In the subsequent derivation-
division step, we will get $r=\partial q/m$, where $\mathfrak{m}$ is the
monomial

$m=\frac{x^{\prime}}{y^{\prime m^{\prime}+1}}$

and such that, $r$ has degree $(m^{\prime},m-1)$. One can verify that such new
polynomial $r$ satisfies the same hypothesis of $p$ (i.e. lies in
$R[x,x^{\prime},y,y^{\prime}]$). Therefore, we conclude by induction
hypothesis that $\mathrm{DD}(r)\leq(m-1)(m^{\prime}+1)+m^{\prime}$. Hence,
since $\mathrm{DD}(p)\leq
m^{\prime}+1+\mathrm{DD}(r)=m(m^{\prime}+1)+m^{\prime}$.

##  2 Studying the number of isolated roots

We are now ready to estimate the the real solutions of equation (1).

For each fixed parameter value $(a,r)\in\mathbb{R}^{2n}$, consider the
sequence of functions $g_{0},f_{1},g_{1},..,f_{n},g_{n}$ defined inductively
as $g_{0}(x)=x$,

$f_{1}(x)=x^{r_{1}},\qquad g_{1}(x)=a_{1}+f_{1}(x)$

and, for each $1\leq i\leq n-1$,

$f_{i+1}(x)=g_{i}(x)^{r_{i+1}},\qquad g_{i+1}(x)=f_{i+1}(x)+a_{i+1}$

As we have seen in the introduction, the functions $f_{i},g_{i}$ are strictly
positive and analytic on some open (possibly unbounded) interval
$I(a,r)\subset\mathbb{R}$. We therefore can consider the subring $G_{n}$ of
$C^{\omega}(I(a,r))$ given by

$G_{n}=r[f_{1}^{\pm},g_{1}^{\pm},\ldots,f_{n}^{\pm},g_{n}^{\pm}]$ (12)

i.e. the ring formed by finite linear combinations of monomials $f^{k}g^{l}$
(with possible negative exponents $k,l$) and coefficients in the ring
$r=\mathbb{Z}[r_{1},..,r_{n}]$.

The following result relates this latter ring with the ring of Laurent
polynomials defined in the previous Section.

######  Proposition 2.1.

The derivation $x\frac{d}{dx}$ maps the ring $G_{n}$ into itself. Moreover, if
we consider the morphism of rings $\Phi:G_{n}\rightarrow\mathbb{L}_{n}$
defined by $\Phi(r_{i})=R_{i}$ and

$\Phi(f_{i})=x_{i},\qquad\Phi(g_{i})=y_{i},\qquad 1\leq i\leq n,$

Then, we have the relation $\partial\circ\Phi=\Phi\circ x\frac{d}{dx}$.

###### Proof.

The proof is immediate. Indeed, we have

$x\frac{d}{dx}f_{1}=x\frac{d}{dx}x^{r_{1}}=r_{1}x^{r_{1}}=r_{1}f_{1}$

Similarly,

$x\frac{d}{dx}f_{2}=x\frac{d}{dx}(a_{2}+(a_{1}+x^{r_{1}})^{r_{2}}=r_{1}r_{2}(a_{2}+(a_{1}+x^{r_{1}})^{r_{2}-1}x^{r_{1}}=(r_{1}r_{2})f_{2}\left(\frac{f_{1}}{g_{1}}\right)$

And, in general,

$x\frac{d}{dx}g_{j}=x\frac{d}{dx}f_{j}=(r_{1}\cdots
r_{j})\,f_{j}\,\frac{f_{1}\cdots f_{j-1}}{f_{1}\cdots f_{j-1}}$

Therefore, comparing with the expressions given in (9), we immediately
conclude that $\partial\circ\Phi=\Phi\circ x\frac{d}{dx}$. ∎

Consider now the analytic function $\varphi:I(a,r)\rightarrow\mathbb{R}$ given
by

$\varphi(x)=a_{n}+(a_{n-1}+\cdots(a_{1}+x^{r_{1}})^{r_{2}}\cdots)^{r_{n}}-bx$
(13)

which we can also write as $\varphi=g_{n}-b\,g_{0}$.

An easy computation shows that
$\psi=x^{2}\left(\frac{d}{dx}\right)^{2}\varphi$ belongs to $G_{n}$. More
specifically, if we consider its image $q=\Phi(\psi)$ under the morphism
$\Phi$ given above and the monomial

$\mathfrak{m}=\frac{x_{1}\cdots x_{n}}{(y_{1}\cdots y_{n-1})^{2}}$

Then, $p=q/m$ is assumes the very simple form

$p=\Delta_{n}\sum_{j=1}^{n}(\Delta_{j}-\Delta_{j-1})\;\left(\prod_{i_{1}=1}^{j-1}x_{i_{1}}\right)\left(\prod_{i_{2}=j}^{n-1}y_{i_{2}}\right)$
(14)

where we define $\Delta_{0}=1$ and recall that $\Delta_{i}=R_{1}\cdots R_{i}$
for $1\leq i\leq n$.

Notation: We denote by $\mathrm{DD}(n)\coloneq\mathrm{DD}(p)$ the number of
steps in the derivation-division algorithm for the above polynomial $p$.

Using the fact that $p\in\mathbb{L}_{n-1}^{\mathrm{reg}}$, we can easily
obtain the following result:

######  Theorem 2.2.

The number of isolated roots of $\varphi$ on $I(a,r)$ (counted with
multiplicities) is bounded by $\mathrm{DD}(n)+2$.

###### Proof.

By Rolle’s Theorem, the number of roots of $\varphi$ on $I(a,r)$ is bounded by
the number of roots of $\psi$ plus two. Let us assume that $\psi$ is not
identically zero. Then, the derivation-division algorithm described in
Corollary 1.8, when to the polynomial applied $p=\frac{\Phi(\psi)}{m}$ given
by (14), defines a sequence of analytic functions on $I(a,r)$ which eventually
(after at most $\mathrm{DD}(n)$ steps) ends up into a constant function.
Therefore, applying again Rolle’s theorem, we conclude that the number of
roots of $\varphi$ on $I(a,r)$ is bounded by $\mathrm{DD}(n)+2$. ∎

Since the number $\mathrm{DD}(n)$ does not depend on any specific choice of
parameters $(a,r)$, we conclude that:

######  Corollary 2.3.

The number $\mathrm{fp}(n)$ (see (4)) is bounded by $\mathrm{DD}(n)+2$.

##  3 At most three solutions for $n=2$

As a simple illustration of the algorithm, let us prove that the equation

$a_{2}+(a_{1}+x^{r_{1}})^{r_{2}}-b\,x=0$ (15)

has a maximum of three isolated solutions. If we denote by $\varphi$ the
right-hand side of the above equation, the function
$\psi=x^{2}\left(\frac{d}{dx}\right)^{2}\varphi$ has the form

$\psi=r_{1}r_{2}\left(r_{1}\left({r_{2}}-1\right)(a_{1}+x^{r_{1}})^{r_{2}-2}x^{2r_{1}-2}+(r_{1}-1)(a_{1}+x^{r_{1}})^{r_{2}-1}x^{r_{1}-2}\right)$

Therefore, upon division by $x^{r_{1}}(a+x^{r_{1}})^{r_{2}-2}$ we obtain

$r_{1}r_{2}\left(r_{1}(r_{2}-1)x^{r_{1}}+(r_{1}-1)(a_{1}+x^{r_{1}})\right)$

which, under the morphism $\Phi$, gives the regular Laurent polynomial

$p=A_{1}x_{1}+B_{1}y_{1}$

where we set $A_{1}=\Delta_{2}(\Delta_{2}-\Delta_{1})$ and
$B_{1}=\Delta_{2}(\Delta_{1}-\Delta_{0})$. Now, applying one step of the
derivation-division, we obtain

$A_{1}x_{1}+B_{1}y_{1}\overset{\partial}{\Longrightarrow}\Delta_{1}(A_{1}+B_{1})x_{1}\overset{\cdot/x_{1}}{\Longrightarrow}\Delta_{1}(A_{1}+B_{1})\in
R$

Therefore, $\mathrm{DD}(n)=1$ and we conclude that $\mathrm{fp}(2)\leq 3$.

The following explicit example shows that indeed $\mathrm{fp}(2)=3$. Take
$a_{1}=0.004259259259$, $a_{2}=-0.1516666667$, $r_{1}=2$ and $r_{2}=1/3$.
Numerical computations with SageMath shows that the equation

$-0.1516666667+(0.004259259259+x^{2})^{1/3}-x=0$

has the three isolated solutions $x_{1}=0.0123409...$, $x_{2}=0.1741525...$
and $x_{3}=0.3585065...$.

##  4 At most five solutions for $n=3$

Let us prove that the equation

$a_{3}+(a_{2}+(a_{1}+x^{r_{1}})^{r_{2}})^{r_{3}}-b\,x=0$ (16)

has a maximum of five solutions, for all parameter values
$(b,(a,r))\in\mathbb{R}_{>0}\times\mathbb{R}^{6}$.

A similar computation to the previous example leads to the polynomial

$p=A_{2}x_{1}x_{2}+B_{2}x_{1}y_{2}+C_{2}y_{1}y_{2}$

where $A_{2}=\Delta_{3}(\Delta_{3}-\Delta_{2})$,
$B_{2}=\Delta_{3}(\Delta_{2}-\Delta_{1})$ and
$C_{2}=\Delta_{3}(\Delta_{1}-\Delta_{0})$.

The following lines show the derivation-division algorithm ends in at most
three steps. We omit the dependence on the coefficients $\Delta_{i}$ to
simplify the notation:

$p^{(0)}=x_{1}x_{2}+x_{1}y_{2}+y_{1}y_{2}$ $\partial
p^{(0)}=\left(x_{1}+\frac{x_{1}^{2}}{y_{1}}\right)x_{2}+x_{1}y_{2}\Longrightarrow
p^{(1)}=\frac{\partial
p^{(0)}}{x_{1}}=\left(1+\frac{x_{1}}{y_{1}}\right)x_{2}+y_{2}$ $\partial
p^{(1)}=\left(\left(\frac{x_{1}}{y_{1}}\right)^{2}+\frac{x_{1}}{y_{1}}\right)x_{2}\Longrightarrow
p^{(2)}=\frac{\partial p^{(1)}}{(x_{1}/y_{1}^{2})x_{2}}=x_{1}+y_{1}$ $\partial
p^{(2)}=x_{1}\Longrightarrow p^{(3)}=\frac{\partial p^{(2)}}{x_{1}}=1$

Therefore, we conclude that $\mathrm{fp}(3)\leq 5$.

The following explicit example shows that indeed $\mathrm{fp}(3)=5$. We take

$a_{3}=-8.39\times
10^{-6},\;\;a_{2}=0.0035836,\;\;a_{1}=-0.012\;\;r_{1}=\frac{53}{150},\;\;r_{2}=\frac{11}{8},\;\;r_{3}=2$

Numerical computations with 20 digits of precision in SageMath give the
following five solutions

$\begin{array}[]{l}x_{1}=0.1270599...\times 10^{-4}\\\
x_{2}=0.1921586...\times 10^{-4}\\\ x_{3}=0.4764392...\times 10^{-4},\\\
x_{4}=0.7949546...\times 10^{-4}\\\ x_{5}=0.2384109...\end{array}$

##  5 Disconjugacy and compensator-type expansions

We now show that, as a byproduct of the derivation-division algorithm, the
function appearing in (1) can be expanded in an uniform basis of functions
satisfying the Chebyshev property.

Firstly, we recall some basic definitions about disconjugate differential
operators. For a thoughtful treatment, we refer the reader to the excellent
Coppel’s book [3]. A $m^{th}$-order linear differential operator $L$ defined
on an interval $I$ is called disconjugate if it can be written in the form

$Lu=\frac{1}{\rho_{m}}\frac{d}{dx}\frac{1}{\rho_{m-1}}\frac{d}{dx}\cdots\frac{d}{dx}\frac{1}{\rho_{0}}u$
(17)

where, for each $0\leq k\leq m$, $\rho_{k}$ is a strictly positive analytic
function on $I$. A well-known result of Polya (see e.g. [3], Chapter 3) states
that $L$ is disconjugate if and only if no solution $u$ of $Lu=0$ has more
than $m-1$ zeros in $I$, counted with multiplicities.

Assuming that $L$ is written as in (17), we can easily construct a basis of
solutions $\\{\omega_{0},\ldots,\omega_{m-1}\\}$ for $L$ as follows: fix an
arbitrary base point $x_{0}\in I$ and set

$\omega_{0}(x)=\rho_{0}(x),\qquad\omega_{1}(x)=\rho_{0}(x)\int_{x_{0}}^{x}\rho_{1}(x_{1})dx_{1}$

and, in general, define $\omega_{k}$ by the $k^{th}$-iterated integral

$\omega_{k}(x)=\rho_{0}(x)\int_{x_{0}}^{x}\rho_{1}(x_{1})\int_{x_{0}}^{x_{1}}\rho_{2}(x_{2})\cdots\int_{x_{0}}^{x_{k-1}}\rho_{k}(x_{k})\,dx_{k}\,\cdots\,dx_{2}\,dx_{1}$
(18)

Notice that this collection of functions has the following properties:

  * (i)

They form a Chebyshev system, i.e. any non-trivial $\mathbb{R}$-linear
combination $\sum\lambda_{k}\omega_{k}(x)$ has at most $m-1$ zeros on $I$.

  * (ii)

For each $0\leq k\leq m-1$, the subset $\\{\omega_{0},\ldots,\omega_{k-1}\\}$
is a basis of solutions of the truncated operator

$L^{[k]}u=\frac{1}{\rho_{k}}\frac{d}{dx}\frac{1}{\rho_{k-1}}\frac{d}{dx}\cdots\frac{d}{dx}\frac{1}{\rho_{0}}u$

(with the convention that $L^{[0]}={1}/{\rho_{0}}$)

  * (iii)

$\omega_{k}(x)$ has a zero of multiplicity precisely $k$ at $x_{0}$ and
$L^{[k]}\omega_{k}=1$.

The last two properties imply that any solution $u$ of $Lu=0$ can be expanded
as

$u(x)=\sum_{k=0}^{m-1}\lambda_{k}\,\omega_{k}(x)$ (19)

where the coefficients $\lambda_{k}\in\mathbb{R}$ are determined inductively
as follows

$\lambda_{m-1}=L^{[m-1]}u,\qquad\lambda_{k-1}=L^{[k-1]}\,\big{(}u-\sum_{j=k}^{m-1}\lambda_{k}u_{k}\big{)},\quad
1\leq k\leq m-1$

Let us now apply these results to our original problem.

For each $n\in\mathbb{N}$ and each parameter value
$(b,a,r)\in\mathbb{R}_{>0}\times\mathbb{R}^{2n}$, we consider the function
$\varphi_{a,r}:I(a,r)\rightarrow\mathbb{R}$ given by (13). Since the parameter
$b$ will be innocuous in the following discussion, we suppose from now on that
$b=1$ and will omit it to simplify the notation.

######  Proposition 5.1.

The function $\varphi_{a,r}$ is a solution of a disconjugate linear
differential operator $L_{a,r}$ of order $\mathrm{DD}(n)+3$.

###### Proof.

We recall from the proof of Theorem 2.2 and Corollary 1.8 that if we set
$\psi=x^{2}\left(\frac{d}{dx}\right)^{2}$ and consider the Laurent polynomial
$q=\Phi(\psi)$ then there exists a sequence of monomials $(\mathfrak{m}_{k})$
for $0\leq k\leq r-1$, such that

$\partial\frac{1}{\mathfrak{m}_{s-1}}\partial\cdots\partial\frac{1}{\mathfrak{m}_{0}}q=0$
(20)

where $s=\mathrm{DD}(n)$ and $\partial$ is the derivation on $\mathbb{L}_{n}$
defined in (9). Using the morphism $\Phi$ defined in Proposition 2.1, this
relation gives $L_{a,r}\varphi_{a,r}=0$, where $L_{a,r}$ is the disconjugate
operator of order $m=s+3$ given by

$L_{a,r}=\frac{d}{dx}\left(\frac{x}{h_{r-1}}\right)\frac{d}{dx}\cdots\left(\frac{x}{h_{0}}\right)\frac{d}{dx}x^{2}\left(\frac{d}{dx}\right)$

In this expression, for each $0\leq j\leq r-1$, we choose
$h_{j}=\Phi^{-1}(\mathfrak{m}_{j})$ to be a function in ring $G_{n}$ (given in
(12)) which is mapped to $\mathfrak{m}_{j}$ under $\Phi$. ∎

In particular, we observe that this result allows to expand $\varphi_{a,r}$ in
terms of a globally defined collection of analytic Chebyshev functions. To
enunciate this result precisely, we consider the open subset in the parameter
space given by

$U=\\{(a,r)\in\mathbb{R}^{2n}\mid I(a,r)\text{ is nonempty }\\}$

Note that, as we have observed in the introduction, $U$ contains in particular
the set of all parameters $(a,r)$ such that $r\in\mathbb{R}^{n}_{>0}$. Now, we
define an open set $V$ in the total space
$\\{(a,r,x)\in\mathbb{R}^{2n}\times\mathbb{R}\\}$ by

$V=\\{\big{(}a,r,I(a,r)\big{)}\mid(a,r)\in U\\}$

######  Proposition 5.2 (Compensator type expansion for $\varphi_{a,r}$).

There exists a collection of $m=\mathrm{DD}(n)+3$ analytic functions
$\\{\omega_{k}\\}_{0\leq k\leq m}$ defined on $V$ such that

  * (i)

For each fixed parameter value $(a,r)$ in $U$, the functions
$\\{x\mapsto\omega_{k}(a,r,x)\\}$ forms a Chebyshev system on $I(a,r)$.

  * (ii)

We can write the expansion

$\varphi_{a,r}(x)=\sum_{k=0}^{m-1}\lambda_{k}(a,r)\,\omega_{k}(a,r,x)$

where the coefficients $\lambda_{k}(a,r)$ are analytic functions on $U$.

###### Proof.

The $m^{th}$-order differential operator $L_{a,r}$ defined in Proposition 17
obviously depends analytically on the parameters $(a,r)\in U$. In other words,
the functions $\rho_{0},..,\rho_{m}$ which appear when we decompose $L_{a,r}$
as (17), are analytic on $V$.

Let $\\{\omega_{k}\\}_{0\leq k\leq m}$ be the basis of solutions of $L_{a,r}$
defined according to (18). Note that the base point $x_{0}$ used in
computation of the iterated integrals must chosen as a point on the interval
$I(a,r)$. Such base point, seen as a function of the parameters $(a,r)$, can
also be chosen to be analytic.

Finally, when we write $\varphi_{a,r}$ in terms of such basis of solutions
$\\{\omega_{k}\\}$, the coefficients $\lambda_{k}(a,r)$ can be computed
according to the recursive procedure described in (19). This shows that they
are analytic functions of $(a,r)$. ∎

We will say that ideal ${\cal I}_{a,r}\subset C^{\omega}(U)$ generated by the
functions $\\{\lambda_{k}\\}_{0\leq k\leq m}$ is the ideal of coefficients of
$\varphi_{a,r}$.

######  Remark 5.3.

Although the functions $\lambda_{k}(a,r)$ obviously depend on the choice of
the basis $\\{\omega_{k}\\}$, the ideal ${\cal{I}}_{a,r}$ itself is
independent of this choice. In fact one can prove that ${\cal{I}}_{a,r}$ is
indeed a polynomial ideal, i.e. generated by polynomials in $\mathbb{Z}[a,r]$.
Let us sketch the proof assuming that $r\in\mathbb{R}_{>0}$: We consider the
Laurent polynomial $q=\Phi(\psi)\in\mathbb{L}_{n}$ defined in the proof of
Proposition 5.1. By definition, we can write a finite expansion

$q=\sum_{j}{c_{j}\,\mathfrak{m}_{j}}$

where $\mathfrak{m}_{j}$ are Laurent monomials and $c_{j}$ are coefficients in
$R=\mathbb{Z}[R_{1},..,R_{n}]$. Under the morphism $\Phi$, each monomial
$\mathfrak{m}_{j}$ corresponds to an analytic function
$h_{j}=\Phi^{-1}(m_{j})$ defined on some open interval containing $+\infty$ on
the boundary. Therefore, we can consider the asymptotic expansion of $h_{j}$
at $x=+\infty$. In fact, a simple application of the binomial expansion to
each monomial shows that the asymptotic expansion of $q$ has the form

$\sum_{\alpha\in S}P_{\alpha}(r,a)x^{\alpha}$

where $S$ is the semigroup
$\mathbb{N}r_{n}+\mathbb{N}r_{n-1}r_{n}+\cdots+\mathbb{N}r_{1}\cdots r_{n}$
and each $P_{j}(r,a)$ is a polynomial in $\mathbb{Z}[a,r]$. Now, it is not
very hard to see that ${\cal{I}}_{a,r}$ is generated by $\langle
P_{\alpha}(r,a)\rangle_{\alpha\in S}$.

######  Example 5.4.

[Classical compensators] Let $n=1$ and consider the function

$\varphi=a+x^{r}-x$

with $r>0$ and $a\in\mathbb{R}$. This function lies in the kernel of the third
order disconjugate linear differential operator

$L=\frac{d}{dx}\frac{1}{x^{r}}\left(\frac{d}{dx}\right)^{2}$

Hence, $\rho_{0}=\rho_{1}=1$ and $\rho_{2}=x^{r-2}$. Let us compute the basis
of solutions $\\{\omega_{0},\omega_{1},\omega_{2}\\}$ by integrating from the
base point $x_{0}=1$. We have $\omega_{0}(x)=1$, $\omega_{1}(x)=x-1$ and

$\omega_{2}(x)=\int_{1}^{x}\Omega(r,y)dy,\quad\text{ where
}\quad\Omega(r,y)=\begin{cases}\log y,&\mbox{ if }r=1,\vspace{0.2cm}\\\
\displaystyle{\frac{y^{r-1}-1}{r-1}},&\mbox{ otherwise}\end{cases}$

is the well-known Ecalle-Roussarie compensator. Explicitly, we obtain

$\omega_{2}(x)=\begin{cases}x\log\left(x\right)-x+1,&\mbox{ if
}r=1,\vspace{0.2cm}\\\ \displaystyle{-\frac{rx-
r-x^{r}+1}{{\left(r-1\right)}r}},&\mbox{ otherwise}\end{cases}$

The ideal of coefficients of ${\cal{I}}_{a,r}$ is generated by the polynomials
$\lambda_{0}=a$, $\lambda_{1}=r-1$ and $\lambda_{2}=r(r-1)$.

Motivated by Roussarie’s result for the saddle loop case [12], we expect that
the generalized compensators introduced in the last Proposition will
ultimately prove useful in analyzing the first return map of non-generic
hyperbolic polycycles.

##  6 The number of steps in the D-D algorithm

We now give an upper estimate on the number $\mathrm{DD}(p)$ of steps of the
derivation-division algorithm, when applied on a given Laurent polynomial
$p\in\mathbb{L}^{\mathrm{reg}}_{n}$. Such bound depends solely on the support
$\mathrm{supp}(p)$, seen as a subset of $\mathbb{Z}^{2n}$.

More precisely, denoting by
$\mathrm{pdeg}(p)=(m_{1},\ldots,m_{n})\in\mathbb{N}^{n}$ the degree of $p$,
let us suppose that

$\mathrm{supp}(p)\subset[0,m_{1}]\times\cdots\times[0,m_{n}]$ (21)

i.e. that $p$ is a homogeneous polynomial in the variables $x_{i},y_{i}$ (with
no negative exponents). For each $1\leq k\leq n$, we denote by

$\mathrm{H}_{k}:\mathbb{N}^{k}\rightarrow\mathbb{N}$

the collection of functions defined recursively as follows:

  * (1)

If $k=1$ then $\mathrm{H}_{1}(m)=m$

  * (2)

If $k\geq 2$ then

    * (2.a)

If $m_{k}=0$ then
$\mathrm{H}_{k}(m_{1},\ldots,m_{k-1},0)=\mathrm{H}_{k-1}(m_{1},\ldots,m_{k-1})$

    * (2.b)

If $m_{k}\geq 1$ then
$\mathrm{H}_{k}(m_{1},\ldots,m_{k-1},m_{k})=\mathrm{H}_{k}(m_{1},\ldots,M_{k-1},m_{k}-1)$,
where $M_{k-1}=m_{k-1}+\mathrm{H}(m_{1},\ldots,m_{k-1})$.

We can now state the following result, whose proof we will omit:

######  Proposition 6.1.

If $\mathrm{supp}(p)$ satisfies the condition (21) then

$\mathrm{DD}(p)\leq\mathrm{H}_{n}(m_{1},\cdots,m_{n}).$

Suppose now that $p$ has the special form given by (14). In this situation,
the support of $p$ is quite special and we conjecture, based on an algorithmic
implementation, that the number $\mathrm{DD}(n)$ is given by

######  Conjecture.

$\mathrm{DD}(n)=A(n-1,1)$.

In the enunciate, $A(n,k)$ denotes the Ackerman function, defined inductively
as follows:

$A(n,k)=\begin{cases}k+1&\mbox{if }n=0\\\ A(n-1,1)&\mbox{if }n>0\mbox{ and
}k=0\\\ A(n-1,A(n,k-1))&\mbox{if }n>0\mbox{ and }k>0.\end{cases}$

Notice that such function grows extremely fast with respect to $n$. Here are
the first 5 values:

$A(0,1)=2,A(1,1)=3,A(2,1)=5,A(3,1)=13,A(4,1)=65533,A(5,1)={2^{2}}^{{\cdot}^{{\cdot}^{{\cdot}^{2}}}}-3$

Here, the rightmost expression is a tower of powers of height $A(4,1)\mbox{ +
3}$.

We conclude by providing a summary of the various upper bounds and the exact
values known for $\mathrm{fp}(n)$:

$n$ | $\mathrm{DD}(n)$ | $\mathrm{K}(n)$ | $\mathrm{SB}(n)$ | Exact Value of $\mathrm{fp}(n)$
---|---|---|---|---
1 | 2 | 8 | 3 | 2
2 | 3 | 5184 | 21 | 3
3 | 5 | $\sim 1.3\times 10^{8}$ | 562 | 5
4 | 13 | $\sim 1.0\times 10^{14}$ | 42554 | ?
5 | 65533 | $\sim 2.0\times 10^{21}$ | $\sim 8.3\times 10^{6}$ | ?

For $n\geq 6$, the $\mathrm{DD}(n)$ bound becomes much larger than both
Khovanskii’s bound $\mathrm{K}(n)$ and Bihan Sotile’s bound $\mathrm{SB}(n)$.

Up to the author’s knowledge, the exact value of $\mathrm{fp}(n)$ is unknown
for $n\geq 4$.

## Declaration

The author states that there is no conflict of interest.

## References

  * [1] Bihan, F.; Sottile, F.New fewnomial upper bounds from Gale dual polynomial system.Moscow Mathematical Journal, 2007, Volume 7, Number 3, Pages 387–407.
  * [2] Cohen, Stephen D.The group of translations and positive rational powers is free. Quart. J. Math. Oxford Ser. (2) 46 (1995), no. 181, 21–93.
  * [3] Coppel, W. A. (1971). Disconjugacy. In Lecture Notes in Mathematics. Springer Berlin Heidelberg. https://doi.org/10.1007/bfb0058618
  * [4] Dumortier F.; Roussarie R. Multi-layer canard cycles and translated power functions, Journal of Differential Equations, Volume 244, Issue 6, 2008, Pages 1329-1358.
  * [5] Ecalle, J. Compensation of small denominators and ramified linearisation of local objects, Astérisque, tome 222 (1994), p. 135-199.
  * [6] Jacquemard, A.; Khechichine-Mourtada F.; Mourtada, A. Algorithmes formels appliqués à l’étude de la cyclicité d’un polycycle algébrique générique à quatre sommets hyperboliques Nonlinearity, Volume 10, Number 1, pp. 19-53.
  * [7] Khovanskii, A.G.Fewnomials, Trans. of Math. Monographs, 88, AMS, 1991.
  * [8] Li, T.; Rojas, J.M.; Wang, X. Counting real connected components of trinomial curve intersections and $m$-nomial hypersurfaces. Discrete Comput. Geom. 30 (2003), no. 3, 379–414.
  * [9] Mourtada, A. Cyclicité finie des polycycles hyperboliques de champs de vecteurs du plan. Algorithme de finitude. Annales de l’Institut Fourier, Volume 41 (1991) no. 3, pp. 719-753.
  * [10] Pauer F.; Unterkircher A. Gröbner Bases for Ideals in Laurent Polynomial Rings and their Application to Systems of Difference Equations. Applicable Algebra in Engineering, Communication and Computing 9 (1999), 271–291.
  * [11] Panazzolo, D. $\mathrm{PSL}(2,\mathbb{C})$, the exponential and some new free groups, The Quarterly Journal of Mathematics, Volume 69, Issue 1, March 2018, 75–117.
  * [12] Roussarie, R. On the number of limit cycles which appear by perturbation of separatrix loop of planar vector fields. Bol. Soc. Bras. Mat 17, 67–101 (1986).
  * [13] Zampieri, Sandro A solution of the Cauchy problem for multidimensional discrete linear shift-invariant systems. Linear Algebra Appl. 202 (1994), 143–162.

D. Panazzolo, IRIMAS, Université de Haute-Alsace, 68093 Mulhouse, France

E-mail address<EMAIL_ADDRESS>