11institutetext: Blavatnik School of Computer Science, Tel Aviv University

# Gradient Adjusting Networks for
Domain Inversion

Erez Sheffi  Michael Rotman  Lior Wolf

###### Abstract

StyleGAN2 was demonstrated to be a powerful image generation engine that
supports semantic editing. However, in order to manipulate a real-world image,
one first needs to be able to retrieve its corresponding latent representation
in StyleGAN’s latent space that is decoded to an image as close as possible to
the desired image. For many real-world images, a latent representation does
not exist, which necessitates the tuning of the generator network. We present
a per-image optimization method that tunes a StyleGAN2 generator such that it
achieves a local edit to the generator’s weights, resulting in almost perfect
inversion, while still allowing image editing, by keeping the rest of the
mapping between an input latent representation tensor and an output image
relatively intact. The method is based on a one-shot training of a set of
shallow update networks (aka. Gradient Modification Modules) that modify the
layers of the generator. After training the Gradient Modification Modules, a
modified generator is obtained by a single application of these networks to
the original parameters, and the previous editing capabilities of the
generator are maintained. Our experiments show a sizable gap in performance
over the current state of the art in this very active domain. Our code is
available at https://github.com/sheffier/gani.

##  1 Introduction

The ability to distinguish between synthetic images and real ones has become
increasingly challenging since the introduction of Generative Adversarial
Networks (GAN) [16]. Although the images produced by this framework are often
indistinguishable from real ones, one lacks the ability to control the
specific outcome. Most relevant to our work is the StyleGAN [23] family of
generators, which can produce, for example, realistic faces based on random
input vectors. However, for most real-world face images, one cannot find an
input vector that would result in exactly the same image.

This is a key limitation of StyleGANs (and other GANs), with far-reaching
implications at the application level. It has been repeatedly shown that the
StyleGAN latent space displays semantic properties that make it especially
suited for image editing applications, see [6] for a survey. However, without
the ability to embed real-world images within this space, these capabilities
are limited mostly to synthetic images.

A set of techniques were, therefore, developed in order to tune the StyleGAN
generator $G$ such that it would produce the desired image [23, 39, 4]. This
has to be done carefully, since performing this tuning too aggressively would
lead to the loss of the semantic properties. While being a very active
research domain, fuelled by many concrete applications, results are still
lacking and the generated copy is still distinctively different from the
desired image.

Existing methods either (i) optimize one image at a time, or (ii) employ
pretrained feedforward networks to produce a modification of $G$, given an
input image $I$. The first category is believed to be more accurate, but
slower at inference time than the second.

Our work combines elements from both approaches – we propose an optimization
procedure for a single image, and our procedure employs trainable networks.
The role of these networks is to estimate the change one wishes to apply to
the parameters of $G$. By optimizing the networks to control this change
rather than applying it directly, we regularize the change being applied. The
per-layer networks we train adapt the parameters of $G$ based on previous
parameter variations. Thus, these changes are applied in a very local manner,
separately to each layer. Through weight sharing, the capacity of these
networks is limited and ensures that this mapping is relatively simple.

In addition to a novel architecture, we also modify the loss term that is used
and show that a face-parsing network provides a strong signal, side by side
with a face-identification network that is widely used in the relevant
literature.

Our results demonstrate: (i) a far more faithful inversion in comparison to
the state-of-the-art methods, (ii) a more limited effect on the result of
applying $G$ to other vectors in its input space, (iii) a superb ability to
support downstream editing applications.

##  2 Related Work

We describe adversarial image generation methods and ways to control the
generated image to fit an input image.

Generative Adversarial Networks  Generative Adversarial Networks (GAN) [16]
are a family of generative models composed of two neural networks: a generator
and a discriminator. The generator is tasked with learning a mapping from a
latent space to a given data distribution, whereas the discriminator aims to
distinguish between generated samples and real ones. GANs have been widely
applied in many computer vision tasks, such as generating super-resolution
images [26, 49], image-to-image translation [57], and face generation [22, 23,
24].

Once trained, given an input vector, the generator produces a realistic image.
Since the mapping between the input vector and the image space is not trivial,
it is hard to predict the generated image from the input vector. One way of
controlling the synthesis is by feeding additional information to the GAN
during the training phase, for instance, by adding additional discrete [32,
35], or continuous [12] labels as inputs. A major caveat in this approach is
that it requires additional supervision. To bypass this limitation, other
approaches constrain the input vector space directly, either by applying tools
from information theory [7] or by limiting this space to a non-trivial
topology [41]. As a result, the input vector space is disentangled: different
entries of the input vector control a different aspect or "generative factor"
of the generated image. It has been observed [37, 23] that a continuous
translation between two vectors in the GAN latent space leads to a continuous
change in the generated image. Shen et al. [42] has further expanded this
observation to face generation, where it was shown that facial attributes lie
in different hyperplanes, and are therefore controllable using vector
arithmetic in the latent space. Further investigation into the latent space
structure has been performed by applying unsupervised methods, such as
Principal Component Analysis (PCA) [18] or eigenvalue decomposition [43], or
by using semantic labels [42, 2]. The existence of an underlying structure,
and the presence of a semantic algebra, make it possible to edit the generated
images.

StyleGAN  StyleGAN [23] is a style-based generator architecture. Unlike the
traditional GAN, which maps a noisy signal directly to images, it splits the
noisy signal into two: (i) a style generating signal $z\in\mathbb{R}^{512}$ to
a style latent space, $w\in W=\mathbb{R}^{512}$, which is used globally as a
set of layer-wise parameters for the GAN (ii) additional noise, which is added
to the feature maps after each convolutional layer. This design benefits from
both stochastic variation and scale-specific feature synthesis. StyleGAN2 [24]
introduced a path-length regularization term that enables smoother style
mapping between $Z$ and $W$, together with a better normalization scheme for
the generator.

Image Editing  By understanding the influence of the different entries in the
latent space, image synthesis can be controlled [7]. Specifically for face
generation, this mapping has been investigated in two directions, unsupervised
and supervised. The unsupervised path aims to unveil the domain’s structure by
applying PCA [18] or eigenvalue decomposition [43]. Other works directly
influence this mapping by conditioning it on supervised labels [42, 2]. The
existence of such an underlying structure, and the understanding of its
algebra, enables the semantic modification of generated images, for instance,
for facial editing [45]. The ability to control the generated samples is a key
aspect of making GANs useful for real-life applications.

Image Inversion  In order to edit a real image using a latent space
modification, the originating point in the latent space has to be identified.
The solutions to the inverse problem can be divided into three families: (i)
optimization-based (ii) encoder-based (iii) generator-modifying. Unlike the
last approach, the first two families do not alter any of the generator
parameters. In the optimization-based approach, a latent code $w^{*}$ is
evaluated given an input image, $I$, in an iterative manner [10, 29], such
that, $I\approx G(w^{*},\theta)$, where $\theta$ are the generator’s
parameters.

For the task of face generation, Karras et al. [24] proposed an optimization-
based inversion scheme for StyleGAN2, where both the latent code $w$ and the
injected noise are optimized together, combined with a regularization term
that minimizes the auto-correlation of the injected noise at different scales.
Abdal et al. [1] extended this direction, by expanding latent space $W$ to
$W^{+}$. To accomplish this, instead of constraining the latent code, $w\in
W$, to be identical for all convolutional layers, each layer is now fed with a
different set of parameters. This modification extended the dimensionality of
the latent code from $\mathbb{R}^{512}$ to $\mathbb{R}^{18\times 512}$. To
preserve spatial details during inversion, Zhanget al. [54] considered a
spatially-structured latent space, replacing the original one-dimensional
representation, $W$.

The second family of solutions is encoder-based. These methods utilize an
encoder, $E$, that maps between the image space and the latent space,
$w^{*}=E\left(I\right)$. Unlike the iterative family, these encoders are
trained on a set of samples [17, 30]. These image encoders have also been
applied for face generation, where they are employed during training, by
combining the auto-encoder framework with a GAN [36], or more commonly, on
pre-trained generative models, which require far less training data. These
approaches focus on mapping an image to an initial latent code, $w\in W$,
which may later be fine-tuned using an optimization method [56]. pSp [38]
employs a different scheme, in which an additional fine-tuning of $w$ is not
performed; instead, a pyramid-based encoder is designed for each style vector
of the StyleGAN2 framework. e4e [46] further expands on this idea by limiting
the hierarchical structure of the $w$ codes to be of a residual type, so that
each style vector is the sum of a basis style vector and a residual part.
Further improvement was achieved for the inversion problem by iteratively
encoding the image onto the latent space and feeding the generated image back
to the encoder as an input [3].

In the last approach, an initial $w$ latent code is evaluated using an
encoder. As a second step, the generator is tuned to produce the required
image from the $w$ [39]. This tuning procedure has been further improved by
employing hypernetworks [4]. In this scenario, instead of directly modifying
the generator weights, a set of residual weights is evaluated using an
additional neural network. The input to this network is the target image.
Therefore, given a new image, a new set of weights is computed.

A faithful edit is also required to preserve the original identity. Liang et
al. [28] applied Neural Spline Networks to find faithful editing directions.
Editing local aspects was accomplished by manipulating specific parts of the
feature maps throughout the generation process [48].

##  3 Method

Our approach adapts a StyleGAN generator for one image at a time by adding a
small correction to the generator’s parameters. This correction is computed
using the novel gradient modification modules, a set of small neural networks
that map between the gradients of the loss criteria with respect to the
generator’s parameters to the parameters’ corrections. During training, only
the parameters of the gradient modification modules are optimized (the
generator parameters are kept frozen) with respect to the loss criteria. The
output of these modules is used to update the parameters of StyleGAN’s
generator, resulting in a new generator that is capable of faithfully
generating the input image. Note that the gradient modification modules are
not added to StyleGAN and that the structure of StyleGAN is not modified at
all.

Given a candidate target image $I$ to be edited, a corresponding latent code,
$w\in W^{+}=\mathbb{R}^{18\times 512}$, is estimated using the off-the-shelf
encoder e4e [46]. The latent code, $w$, is fed into the pre-trained generator
to produce a reconstructed image, $G(w)=G(w,\theta)$, where the right-hand
side explicitly states the parameters $\theta$ of network $G$. Since $w$ is
not an exact solution to the inverse problem, the reconstructed image is
usually of poor quality. In our method, $w$ does not change. Instead, we tune
the generator parameters $\theta$ to improve the generated image, obtaining
$G(w,\theta^{\prime})\sim I$, where $\theta^{\prime}$ are the tuned
parameters.

Consider the following image similarity loss function,

$\textstyle\mathcal{L}\left(I_{1},I_{2}\right)=\lambda_{1}\mathcal{L}_{\text{rec}}+\lambda_{2}\mathcal{L}_{lpips}+\lambda_{3}\mathcal{L}_{sim}+\lambda_{4}\mathcal{L}_{FP}\,,$
(1)

which is the sum of four terms. The first term is a pixel-wise reconstruction
loss, the $L_{2}$ or the $L_{1}^{\text{smooth}}$ [15] distance between the
images $I_{1}$ and $I_{2}$. The second term, $\mathcal{L}_{lpips}$, is a
perceptual similarity loss [55], that relies on feature maps from a pre-
trained AlexNet [44] on the ImageNet dataset. $\mathcal{L}_{sim}$ is an
identity-preserving similarity loss that is applied on a pair of real and
reconstructed images. This loss term accounts for the cosine distance of
feature vectors extracted from a pre-trained ArcFace [11] facial recognition
network for the facial domain, and a pre-trained MoCo [8] for the non-facial
domains, following [46, 4]. The last term is a multi-layer face-parsing loss,
$\mathcal{L}_{FP}$. Similarly to $\mathcal{L}_{sim}$, it measures the layer-
wise aggregated cosine distance of all the feature vectors from the
contracting path of the pre-trained facial parsing network P [27], with a
U-Net [40] backbone. In total, 5 feature vectors are used for the cosine
distance evaluation.

Tuning the $G$’s parameters, $\theta$, involves the estimation of the modified
parameters, $\theta^{\prime}$, using a set of feed-forward networks. Let
$l_{i}$ be the $i$th layer of $G$, and let $\theta_{i}$ and
$\frac{\partial\mathcal{L}}{\partial\theta_{i}}$ be its learnable parameters
and the gradients of the objective function w.r.t to these parameters,
respectively. Unlike PTI [39], which applies a regular gradient step to update
$\theta_{i}$, the gradient updates are based on the mapping,

$\textstyle\theta_{i}^{\prime}=\theta_{i}\odot\left(1+\Delta\theta_{i}\right)=\theta_{i}\odot\left(1+M_{i}\left(\frac{\partial\mathcal{L}}{\partial\theta_{i}}\right)\right)\,,$
(2)

where $\mathcal{M}=\left\\{M_{i}\right\\}$ is a set of gradient modification
modules, each mapping between the original gradients,
$\frac{\partial\mathcal{L}}{\partial\theta_{i}}$, and the parameter
correction, $\Delta\theta_{i}$.

Each module $M_{i}$ contains a sequential set of $l=1\dots L$ residual blocks
[20]. Let $y_{l}$ be the input to the $l$th residual block. The output of
block $l$, $y_{l+1}$ is then:

$\displaystyle\textstyle r$
$\displaystyle=W_{2}^{l}\sigma\left(\text{SN}^{l}_{2}\left(W_{1}^{l}\sigma\left(\text{SN}^{l}_{1}\left(y_{l}\right)\right)\right)\right)+b^{l}$
(3) $\displaystyle y_{l+1}$ $\displaystyle=y_{l}+r\,,$ (4)

where $\sigma$ is the LeakyReLU [31] activation function, with a slope of
$0.01$ and SN is the Scale Normalization (SN) [34]. The learnable parameters
of each block reside in two linear operators, $W_{1}^{l}$ and $W_{2}^{l}$, in
the bias term, $b^{l}$, and in the scale coefficient of the SN layer. The
parameters of $W^{l}_{1}$ and $W^{l}_{2}$ are initialized according to [19]
from the normal distribution, with an initial standard deviation factored by
$0.1$, whereas the bias, $b^{l}$ is sampled uniformly.

Figure 1: The structure of one residual block of a gradient modification
module, $\mathcal{M}_{i}$. The input to the first block, $y_{0}$ is,
$\frac{\partial\mathcal{L}}{\partial\theta_{i}}$.

All the $M_{i}$ networks assigned to convolutional layers with the number of
channels, $c_{in}=c_{out}=512$, share the same parameters,
$\psi_{i}=\left\\{W^{l}_{1},W^{l}_{2},b^{l},\text{SN}^{l}_{1},\text{SN}^{l}_{2}\right\\}_{l=1}^{L}$.
During optimization, (only) the parameters $\left\\{\psi_{i}\right\\}$ of the
set $\mathcal{M}$ are optimized to minimize the loss function,

$\textstyle\mathcal{L}_{total}=\lambda_{e}\mathcal{L}\left(I,G(w,\theta^{\prime})\right)+\lambda_{l}\mathcal{L}\left(G(f(z),\theta),G(f(z),\theta^{\prime})\right)\,$
(5)

where $z\sim\mathcal{N}\left(0,\mathds{1}\right)\in\mathbb{R}^{512}$, and $f$
is the style mapping of StyleGAN [23] so style mapping, $f(z)$ lies in $W$
(and not in $W^{+}$). The first term in Eq. (5) is responsible for generating
a high-quality image. It is crucial that the optimization procedure should not
dramatically alter the mapping $G:w\rightarrow I$ as a large variation in the
mapping would require the re-identification of the editing directions. The
second term in Eq. (5), a localization regularizer [39, 33], prevents the
generator from drifting by forcing the generator to produce identical images
for randomly sampled latent codes. An outline of our method appears in
Algorithm 1.

Algorithm 1 Method Outline

Image $I$, generator $G_{\theta}$, encoder $E$, $\mathcal{M}$

$G(w,\theta^{\prime})$

$w\leftarrow E(I)$ $\triangleright$ Obtain $w$ from a pre-trained encoder

for $i\in 1\dots n_{\text{iterations}}$ do

Compute $\frac{\partial\mathcal{L}(I,G(w,\theta))}{\partial\theta}$

for $M_{i}\in\mathcal{M}$ do

$\Delta\theta_{i}=M_{i}\left(\frac{\partial\mathcal{L}}{\partial\theta_{i}}\right)$
$\triangleright$ $\mathcal{L}$ in Eq. (1)

end for

Sample $z\sim\mathcal{N}\left(0,\mathds{1}\right)\in\mathbb{R}^{512}$
$\triangleright$ Localization

Compute $\frac{\partial\mathcal{L}_{total}}{\partial\psi}$ $\triangleright$
$\mathcal{L}_{total}$ in Eq. (5)

Update the parameters $\psi$ of $\mathcal{M}$

end for

##  4 Experiments

We conduct an extensive set of experiments on various image synthesis
datasets. For all image domains, our method utilizes a pre-trained StyleGAN2.
For the facial domain, this pre-trained network was optimized for generating
facial images distributed according to the FFHQ [23] dataset, whereas the
inversion and editing capabilities of our approach are evaluated over images
from the test set of the Celeb-HQ [22] dataset. Our method is also evaluated
on Church and Horses from the LSUN [53] dataset, on automobiles from Stanford
Cars [25], and on wildlife images from AFHQ-WILD [9]. The pre-trained models
for these domains were acquired from the e4e [46] and HyperStyle [4] official
GitHub repositories. The initial inverted vectors, $w\in W^{+}$, were also
obtained using the e4e encoders in these repositories. Since there is no pre-
trained encoder to $W^{+}$ space for the AFHQ-WILD dataset, our method is
evaluated on this using the $W$ latent space.

For all experiments, the Ranger [51] optimizer was used, with a learning rate
of $0.001$. The number of iterations and the loss coefficients used for our
method appears in Table 1. For the CelebA-HQ and AFHQ-Wild datasets,
$\mathcal{L}_{\text{pixel-wise}}=L_{2}$ and for Stanford Cars, LSUN Church,
and LSUN Horses, $\mathcal{L}_{\text{pixel-wise}}=L_{1}^{\text{smooth}}$ with
$\beta=0.1$. The difference in the number of iterations depends on the quality
of the reconstruction of the original generator $G$ from $w$. Both LSUN Church
and LSUN Horses resulted in a poor initial reconstruction and required twice
as many iterations.

Table 1: The loss coefficients and number of running iterations that were used by our method for each of the different datasets. | Iterations | $\lambda_{e}$ | $\lambda_{l}$ | $\lambda_{1}$ | $\lambda_{2}$ | $\lambda_{3}$ | $\lambda_{4}$
---|---|---|---|---|---|---|---
CelebA-HQ | 300 | 1.0 | 0.2 | 1.0 | 0.8 | 0.1 | 1.0
AFHQ-Wild | 300 | 1.0 | 0.2 | 1.0 | 0.8 | 0.1 | 1.0
Stanford Cars | 400 | 1.0 | 0.2 | 1.0 | 0.8 | 0.1 | -
LSUN Horses | 800 | 1.0 | 0.2 | 1.0 | 0.8 | 0.1 | -
LSUN Church | 800 | 1.0 | 0.2 | 1.0 | 0.8 | 0.1 | -

Table 2 presents four evaluation criteria for reconstruction quality over the
CelebA-HQ dataset. The four metrics compare the input image $I$ with the one
generated by the inversion method, $G(w,\theta^{\prime})$. These metrics are
the pixel-wise similarity, which is the Euclidean norm $L_{2}$, the perceptual
similarity, LPIPS [55], the structural similarity score, MS-SSIM [50], and
identity similarity, ID [21], between the input image, $I$, and its
reconstruction, $G(w,\theta^{\prime})$. Our method outperforms all other
methods in all metrics except LPIPS, where the original StyleGAN2 inversion
approach matches ours.

Table 2: Reconstruction metrics on the CelebA-HQ test set. Method |  $\uparrow$ID |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---|---
StyleGAN2 [24] | $0.78$ | $0.90$ | $0.020$ | $0.090$
PTI [39] | $0.85$ | $0.92$ | $0.090$ | $0.015$
IDInvert [56] | $0.18$ | $0.68$ | $0.220$ | $0.061$
pSp [38] | $0.56$ | $0.76$ | $0.170$ | $0.034$
e4e [46] | $0.50$ | $0.72$ | $0.200$ | $0.052$
$\text{ReStyle}_{\text{pSp}}$ [3] | $0.66$ | $0.79$ | $0.130$ | $0.030$
$\text{ReStyle}_{\text{e4e}}$ [3] | $0.52$ | $0.74$ | $0.190$ | $0.041$
NP-GAN-I [14] | $-$ | $-$ | $0.283$ | $0.004$
HyperStyle [4] | $0.76$ | $0.84$ | $0.090$ | $0.019$
HFGI [5] | $-$ | $-$ | $0.100$ | $0.021$
HyperInverter [13] | $0.60$ | $0.67$ | $0.105$ | $0.024$
Feature-Style Encoder [52] | $0.87$ | $-$ | $0.066$ | $0.019$
Ours | $\mathbf{0.99}$ | $\mathbf{0.97}$ | $\mathbf{0.020}$ | $\mathbf{0.003}$

Table 3 evaluates the reconstruction quality for the Stanford Cars dataset,
Table 4 for the AFHQ-Wild dataset, Table 5 for the LSUN church dataset and
Table 6 for the LSUN horses dataset, using three evaluation criteria: the
pixel-wise Euclidean norm, $L_{2}$, the perceptual similarity, LPIPS, and the
MS-SSIM [50] score. Our method outperforms all other methods on the AFHQ-Wild
and LSUN church datasets. In the Stanford Cars and the LSUN horses datasets,
our approach surpasses other approaches in all evaluation metrics, except for
the $L_{2}$ metric, where it is second to Near Perfect GAN Inversion (NP-
GAN-I) [14].

Table 3: Reconstruction metrics on the Stanford Cars dataset [25] test set. Method |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---
StyleGAN2 [24] | $0.79$ | $0.16$ | $0.060$
PTI [39] | $0.93$ | $0.11$ | $0.010$
pSp [38] | $0.58$ | $0.29$ | $0.100$
e4e [46] | $0.53$ | $0.32$ | $0.120$
$\text{ReStyle}_{\text{pSp}}$ [3] | $0.66$ | $0.25$ | $0.070$
$\text{ReStyle}_{\text{e4e}}$ [3] | $0.60$ | $0.29$ | $0.090$
HyperStyle [4] | $0.67$ | $0.27$ | $0.070$
NP-GAN-I [14] | $-$ | $0.15$ | $\mathbf{0.006}$
Ours | $\mathbf{0.94}$ | $\mathbf{0.03}$ | $0.010$
Table 4: Reconstruction metrics for AFHQ-Wild test set. Method |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---
StyleGAN2 [24] | $0.82$ | $0.13$ | $0.030$
PTI [39] | $0.93$ | $0.08$ | $0.010$
pSp [38] | $0.51$ | $0.35$ | $0.130$
e4e [46] | $0.47$ | $0.36$ | $0.140$
$\text{ReStyle}_{\text{pSp}}$ [3] | $0.57$ | $0.21$ | $0.050$
$\text{ReStyle}_{\text{e4e}}$ [3] | $0.52$ | $0.25$ | $0.070$
HyperStyle [4] | $0.56$ | $0.24$ | $0.060$
NP-GAN-I [14] | $-$ | $0.38$ | $0.014$
Ours | $\mathbf{0.96}$ | $\mathbf{0.03}$ | $\mathbf{0.006}$
Table 5: Reconstruction metrics on the LSUN churches [53] (outdoor) test set. Method |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---
StyleGAN2 [24] | $0.4797$ | $0.325$ | $0.167$
PTI [39] | $0.6968$ | $0.097$ | $0.051$
pSp [38] | $0.4070$ | $0.310$ | $0.130$
e4e [24] | $0.3481$ | $0.420$ | $0.140$
ReStyle [3] | $0.3878$ | $0.377$ | $0.127$
HFGI [5] | $-$ | $0.220$ | $0.090$
HyperInverter [52] | $0.5762$ | $0.223$ | $0.091$
Ours | $\mathbf{0.9479}$ | $\mathbf{0.015}$ | $\mathbf{0.014}$
Table 6: Reconstruction metrics for LSUN horses. Method |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---
e4e [24] | $0.25$ | $0.431$ | $0.1740$
ReStyle [3] | $-$ | $0.525$ | $0.159$
NP-GAN-I [14] | $-$ | $0.141$ | $\mathbf{0.005}$
Ours | $\mathbf{0.94}$ | $\mathbf{0.016}$ | $0.010$

Inversion Quality  We begin with a qualitative evaluation of reconstructed
images. Fig. 2 demonstrates the reconstruction of facial images taken from the
CelebA-HQ [22] dataset, and Fig. 3 demonstrates the reconstruction of car
images taken from the Stanford Cars [25] dataset. We compare the reconstructed
images produced by our method with the following previous approaches: pSp
[38], e4e [46], $\text{ReStyle}_{\text{pSp}}$ [3],
$\text{ReStyle}_{\text{e4e}}$ [3], HyperStyle [4].

|  |  |  |  |  |
---|---|---|---|---|---|---
|  |  |  |  |  |
|  |  |  |  |  |
GT | pSp | e4e | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | Ours
Figure 2: Visual comparison of image reconstruction quality on CelebA-HQ. |  |  |  |  |  |
---|---|---|---|---|---|---
|  |  |  |  |  |
|  |  |  |  |  |
GT | pSp | e4e | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | ours
Figure 3: Visual comparison of image reconstruction quality on the Stanford
Cars.

As can be seen in Fig. 2, our method is able to generate almost identical
reconstructions. The first and third rows demonstrate the reconstruction of
difficult examples. Our method is able to produce near-identical
reconstruction, whereas all other methods struggle to achieve inversion of
good quality. The second row demonstrates the reconstruction of a relatively
easy example. Although all methods are able to produce meaningful
reconstruction, only our method is truly able to preserve identity and
properly reconstruct fine details (such as gaze, eye color, dimples, etc.).

As can be seen in Fig. 3, there is a large gap between our method and the
other ones. Specifically, all baseline methods struggle to reconstruct various
elements (fine or coarse). In all three rows, only our method is able to
reconstruct the coarse shape of the car properly. In the first row, we can see
that only our method is able to reconstruct the following elements properly:
(i) the coarse shape of the car, (ii) the shape of the headlight, (iii) the
fact that the lights are on, (iv) the absence of a roof, (v) the car’s logo.
In the second row, only our method is able to reconstruct the following
elements properly: (i) shape of the headlights, (ii) side-mirrors, (iii) color
tone, (iv) reflection. In the third row, only our method is able to
reconstruct the following elements properly: (i) wheels, (ii) placement and
size of the passenger window, (iii) side-mirror shape and color.

|  |  |  |  |  |
---|---|---|---|---|---|---
GT | PTI | StyleGAN2 | e4e | ReStyle | HI | Ours
Figure 4: Visual comparison of image reconstruction quality on the LSUN
Church. HI stands for HyperInverter [52]

To test the effect of the number of residual blocks, $L$, of the gradient
modification modules, the image reconstruction performance of our approach was
evaluated for 200 randomly sampled images from the CelebA-HQ test set. As
Table 7 shows, adding more blocks slightly improves the image quality scores
of the MS-SSIM, LPIPS, and $L_{2}$ metrics, whereas it hardly degrades the
identity preservation score.

Table 7: The effect of the number of residual blocks, $L$, on image reconstruction. These results are obtained on a fixed evaluation set consisting of 200 randomly sampled images from the CelebA-HQ test set. $L$ | # Parameters |  $\uparrow$ID |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---|---|---
$1$ | $1,396,658$ | $\mathbf{0.99773}$ | $0.9739$ | $0.0201$ | $0.0033$
$2$ | $2,793,316$ | $0.99769$ | $0.9778$ | $0.0177$ | $0.0028$
$3$ | $4,189,974$ | $0.99751$ | $0.9785$ | $0.0170$ | $0.0027$
$4$ | $5,586,632$ | $0.99729$ | $\mathbf{0.9790}$ | $\mathbf{0.0167}$ | $\mathbf{0.0026}$

In order to assess the contribution of the normalization scheme utilized by
our approach our model was evaluated on the first 200 samples from the test
set of CelebA-HQ. First, we test whether the inputs to the module $M_{i}$ have
to be normalized using SN, Instance Normalization (IN) [47], or kept
untouched. Additionally, we test which normalization scheme should be applied
inside each residual block. Table 8 summarizes the different normalization
choices. As can be seen, not applying normalization in the residual block
harms all evaluation metrics, whereas normalizing the inputs prior to feeding
them into the gradient modification modules, $M_{i}$, is not necessary.

Table 8: Different normalization schemes applied to 200 samples from the test set of the CelebA-HQ dataset. PreNorm stands for normalizing the inputs prior to the application of $M_{i}$, and PostNorm stands for the normalization scheme applied in each residual block. SN is the Scale Normalization [34] and IN is the one-dimensional Instance Normalization [47]. | PreNorm | PostNorm |  $\uparrow$ID |  $\uparrow$MS-SSIM |  $\downarrow$LPIPS |  $\downarrow$ $L_{2}$
---|---|---|---|---|---|---
(a) | $-$ | $-$ | $0.834$ | $0.765$ | $0.172$ | $0.039$
(b) | $-$ | IN | $0.996$ | $0.996$ | $0.030$ | $0.005$
(c) | $-$ | SN | $\mathbf{0.998}$ | $\mathbf{0.998}$ | $\mathbf{0.020}$ | $\mathbf{0.003}$
(d) | IN | $-$ | $0.895$ | $0.802$ | $0.151$ | $0.032$
(e) | IN | IN | $0.997$ | $0.974$ | $0.021$ | $0.003$
(f) | IN | SN | $0.998$ | $0.973$ | $0.021$ | $0.003$
(g) | SN | $-$ | $0.997$ | $0.778$ | $0.168$ | $0.037$
(h) | SN | IN | $0.857$ | $0.972$ | $0.023$ | $0.004$
(i) | SN | SN | $0.997$ | $0.974$ | $0.021$ | $0.003$

Editing Quality  The ability of our method to retain the original editing
directions of StyleGAN is seen in Fig. 5 for the CelebA-HQ dataset, editing
directions and tools were taken from InterFaceGAN [42]. A visual comparison to
other approaches for Stanford Cars and LSUN Church datasets appears in Fig. 7
and Fig. 6, respectively. For these datasets, the editing directions were
taken from GANSpace [18]. Evidently, unlike other approaches, our method is
able to retain the editing direction without harming image quality, for
instance, on the automotive images, it is the only approach that modifies the
color uniformly, whereas in the outdoor image in Fig. 6, it does not introduce
artifacts or change the image’s content.

Source | Pose | Smile | Age
---|---|---|---
|  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |  |
Figure 5: Pose, smile and age editing using InterFaceGAN [42] on CelebA-HQ. -Blue Skies |  |  |  |  |
---|---|---|---|---|---
-Clouds |  |  |  |  |
+Clouds |  |  |  |  |
-Vibrant |  |  |  |  |
+Vibrant |  |  |  |  |
| GT | e4e | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | Ours
Figure 6: Editing quality on LSUN Church using GANSpace [18] +Color |  |  |  |  |  |  |
---|---|---|---|---|---|---|---
+Cube |  |  |  |  |  |  |
| GT | pSp | e4e | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | Ours
Figure 7: Editing quality on the Stanford Cars using GANSpace [18]

Face-Parsing Loss  Fig. 8 shows the benefits of applying the face-parsing loss
to images from the CelebA-HQ and AFHQ-Wild datasets. As can be seen, for the
facial image, the reconstructed image retains the fine details in the lips
when the parsing loss is applied. Furthermore, even though the parsing loss
utilizes a pre-trained network, trained on the task of human facial semantic
segmentation, it also improves the reconstruction quality for other non-human
facial domains.

CelebA-HQ |  |  |
---|---|---|---
AFHQ-Wild |  |  |
| (a) | (b) | (c)
Figure 8: Visual comparison of the effect of training with $\mathcal{L}_{FP}$.
(a) Ground truth (b) with $\mathcal{L}_{FP}$ (c) without $\mathcal{L}_{FP}$.

Localization Regularization  The localization term prevents model drifting,
which is often manifested as additional artifacts. As seen in Fig. 9, it is
helpful in preventing the diffusion of the skin color to the teeth.

|
---|---
(a) | (b)
Figure 9: Image reconstruction. (a) with localization. (b) without
localization

##  5 Conclusions

The proliferation of work devoted to effectively inverting StyleGANs indicates
an acute need for such technologies, in order to perform image editing and
semantic image manipulations. In this work, we present a novel method that
employs learned mappings between the loss gradient of a layer and a suggested
shift to the layer’s parameters. These shifts are used within an iterative
optimization process, in order to fine-tune the StyleGAN generator. The
learning of the mapping networks and the optimization of the generator occur
concurrently and on a single sample.

We conduct a set of experiments that is considerably more extensive than what
has been presented in recent relevant contributions, showing that the modified
generator produces the target image more accurately than all other methods in
this very active field. Moreover, it supports downstream editing tasks more
convincingly than the alternatives.

###  5.0.1 Acknowledgements

This project has received funding from the European Research Council (ERC)
under the European Unions Horizon 2020 research, innovation program (grant ERC
CoG 725974).

## References

  * [1] Abdal, R., Qin, Y., Wonka, P.: Image2stylegan: How to embed images into the stylegan latent space? 2019 IEEE/CVF International Conference on Computer Vision (ICCV) pp. 4431–4440 (2019)
  * [2] Abdal, R., Zhu, P., Mitra, N.J., Wonka, P.: Styleflow: Attribute-conditioned exploration of stylegan-generated images using conditional continuous normalizing flows. ACM Transactions on Graphics (TOG) 40(3), 1–21 (2021)
  * [3] Alaluf, Y., Patashnik, O., Cohen-Or, D., et al.: Restyle: A residual-based stylegan encoder via iterative refinement. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) (October 2021)
  * [4] Alaluf, Y., Tov, O., Mokady, R., Gal, R., Bermano, A.H.: Hyperstyle: Stylegan inversion with hypernetworks for real image editing. arXiv preprint arXiv:2111.15666 (2021)
  * [5] Bai, Q., Xu, Y., Zhu, J., Xia, W., Yang, Y., Shen, Y.: High-fidelity gan inversion with padding space. ArXiv abs/2203.11105 (2022)
  * [6] Bermano, A.H., Gal, R., Alaluf, Y., Mokady, R., Nitzan, Y., Tov, O., Patashnik, O., Cohen-Or, D.: State-of-the-art in the architecture, methods and applications of stylegan. arXiv preprint arXiv:2202.14020 (2022)
  * [7] Chen, X., Duan, Y., Houthooft, R., Schulman, J., Sutskever, I., Abbeel, P.: Infogan: Interpretable representation learning by information maximizing generative adversarial nets. Advances in neural information processing systems 29 (2016)
  * [8] Chen, X., Fan, H., Girshick, R.B., He, K.: Improved baselines with momentum contrastive learning. ArXiv abs/2003.04297 (2020)
  * [9] Choi, Y., Uh, Y., Yoo, J., Ha, J.W.: Stargan v2: Diverse image synthesis for multiple domains. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2020)
  * [10] Creswell, A., Bharath, A.A.: Inverting the generator of a generative adversarial network. IEEE transactions on neural networks and learning systems 30(7), 1967–1974 (2018)
  * [11] Deng, J., Guo, J., Xue, N., Zafeiriou, S.: Arcface: Additive angular margin loss for deep face recognition. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 4690–4699 (2019)
  * [12] Ding, X., Wang, Y., Xu, Z., Welch, W.J., Wang, Z.J.: Cc{gan}: Continuous conditional generative adversarial networks for image generation. In: International Conference on Learning Representations (2021), https://openreview.net/forum?id=PrzjugOsDeE
  * [13] Dinh, T.M., Tran, A., Nguyen, R.H.M., Hua, B.S.: Hyperinverter: Improving stylegan inversion via hypernetwork. ArXiv abs/2112.00719 (2021)
  * [14] Feng, Q., Shah, V., Gadde, R., Perona, P., Martinez, A.: Near perfect gan inversion. ArXiv abs/2202.11833 (2022)
  * [15] Girshick, R.: Fast r-cnn. In: Proceedings of the IEEE international conference on computer vision. pp. 1440–1448 (2015)
  * [16] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. Advances in neural information processing systems 27 (2014)
  * [17] Guan, S., Tai, Y., Ni, B., Zhu, F., Huang, F., Yang, X.: Collaborative learning for faster stylegan embedding. arXiv preprint arXiv:2007.01758 (2020)
  * [18] Härkönen, E., Hertzmann, A., Lehtinen, J., Paris, S.: Ganspace: Discovering interpretable gan controls. Advances in Neural Information Processing Systems 33, 9841–9850 (2020)
  * [19] He, K., Zhang, X., Ren, S., Sun, J.: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In: Proceedings of the IEEE international conference on computer vision. pp. 1026–1034 (2015)
  * [20] He, K., Zhang, X., Ren, S., Sun, J.: Identity mappings in deep residual networks. In: European conference on computer vision. pp. 630–645. Springer (2016)
  * [21] Huang, Y., Wang, Y., Tai, Y., Liu, X., Shen, P., Li, S., Li, J., Huang, F.: Curricularface: adaptive curriculum learning loss for deep face recognition. In: proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 5901–5910 (2020)
  * [22] Karras, T., Aila, T., Laine, S., Lehtinen, J.: Progressive growing of gans for improved quality, stability, and variation. arXiv preprint arXiv:1710.10196 (2017)
  * [23] Karras, T., Laine, S., Aila, T.: A style-based generator architecture for generative adversarial networks. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 4401–4410 (2019)
  * [24] Karras, T., Laine, S., Aittala, M., Hellsten, J., Lehtinen, J., Aila, T.: Analyzing and improving the image quality of stylegan. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 8110–8119 (2020)
  * [25] Krause, J., Stark, M., Deng, J., Fei-Fei, L.: 3d object representations for fine-grained categorization. In: 4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13). Sydney, Australia (2013)
  * [26] Ledig, C., Theis, L., Huszár, F., Caballero, J., Cunningham, A., Acosta, A., Aitken, A., Tejani, A., Totz, J., Wang, Z., et al.: Photo-realistic single image super-resolution using a generative adversarial network. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 4681–4690 (2017)
  * [27] Lee, C.H., Liu, Z., Wu, L., Luo, P.: Maskgan: Towards diverse and interactive facial image manipulation. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2020)
  * [28] Liang, H., Hou, X., Shen, L.: Ssflow: Style-guided neural spline flows for face image manipulation. In: Proceedings of the 29th ACM International Conference on Multimedia. pp. 79–87 (2021)
  * [29] Ling, H., Kreis, K., Li, D., Kim, S.W., Torralba, A., Fidler, S.: Editgan: High-precision semantic image editing. In: Advances in Neural Information Processing Systems (NeurIPS) (2021)
  * [30] Luo, J., Xu, Y., Tang, C., Lv, J.: Learning inverse mapping by autoencoder based generative adversarial nets. In: International Conference on Neural Information Processing. pp. 207–216. Springer (2017)
  * [31] Maas, A.L., Hannun, A.Y., Ng, A.Y., et al.: Rectifier nonlinearities improve neural network acoustic models. In: Proc. icml. p. 3. Citeseer (2013)
  * [32] Mirza, M., Osindero, S.: Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 (2014)
  * [33] Mitchell, E., Lin, C., Bosselut, A., Finn, C., Manning, C.D.: Fast model editing at scale. CoRR (2021), https://arxiv.org/pdf/2110.11309.pdf
  * [34] Nguyen, T.Q., Salazar, J.: Transformers without tears: Improving the normalization of self-attention. arXiv preprint arXiv:1910.05895 (2019)
  * [35] Odena, A., Olah, C., Shlens, J.: Conditional image synthesis with auxiliary classifier gans. In: International conference on machine learning. pp. 2642–2651. PMLR (2017)
  * [36] Pidhorskyi, S., Adjeroh, D.A., Doretto, G.: Adversarial latent autoencoders. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 14104–14113 (2020)
  * [37] Radford, A., Metz, L., Chintala, S.: Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434 (2015)
  * [38] Richardson, E., Alaluf, Y., Patashnik, O., Nitzan, Y., Azar, Y., Shapiro, S., Cohen-Or, D.: Encoding in style: a stylegan encoder for image-to-image translation. arXiv preprint arXiv:2008.00951 (2020)
  * [39] Roich, D., Mokady, R., Bermano, A.H., Cohen-Or, D.: Pivotal tuning for latent-based editing of real images. arXiv preprint arXiv:2106.05744 (2021)
  * [40] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [41] Rotman, M., Dekel, A., Gur, S., Oz, Y., Wolf, L.: Unsupervised disentanglement with tensor product representations on the torus. In: International Conference on Learning Representations (2022)
  * [42] Shen, Y., Gu, J., Tang, X., Zhou, B.: Interpreting the latent space of gans for semantic face editing. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 9243–9252 (2020)
  * [43] Shen, Y., Zhou, B.: Closed-form factorization of latent semantics in gans. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 1532–1540 (2021)
  * [44] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014)
  * [45] Tewari, A., Elgharib, M., Bharaj, G., Bernard, F., Seidel, H.P., Pérez, P., Zollhofer, M., Theobalt, C.: Stylerig: Rigging stylegan for 3d control over portrait images. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 6142–6151 (2020)
  * [46] Tov, O., Alaluf, Y., Nitzan, Y., Patashnik, O., Cohen-Or, D.: Designing an encoder for stylegan image manipulation. ACM Transactions on Graphics (TOG) 40(4), 1–14 (2021)
  * [47] Ulyanov, D., Vedaldi, A., Lempitsky, V.: Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv:1607.08022 (2016)
  * [48] Wang, R., Chen, J., Yu, G., Sun, L., Yu, C., Gao, C., Sang, N.: Attribute-specific control units in stylegan for fine-grained image manipulation. In: Proceedings of the 29th ACM International Conference on Multimedia. pp. 926–934 (2021)
  * [49] Wang, X., Yu, K., Wu, S., Gu, J., Liu, Y., Dong, C., Qiao, Y., Change Loy, C.: Esrgan: Enhanced super-resolution generative adversarial networks. In: Proceedings of the European conference on computer vision (ECCV) workshops. pp. 0–0 (2018)
  * [50] Wang, Z., Simoncelli, E.P., Bovik, A.C.: Multiscale structural similarity for image quality assessment. In: The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, 2003. vol. 2, pp. 1398–1402. Ieee (2003)
  * [51] Wright, L.: Ranger - a synergistic optimizer. https://github.com/lessw2020/Ranger-Deep-Learning-Optimizer (2019)
  * [52] Yao, X., Newson, A., Gousseau, Y., Hellier, P.: Feature-style encoder for style-based gan inversion. ArXiv abs/2202.02183 (2022)
  * [53] Yu, F., Seff, A., Zhang, Y., Song, S., Funkhouser, T., Xiao, J.: LSUN: Construction of a large-scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv:1506.03365 (2015)
  * [54] Zhang, L., Bai, X., Gao, Y.: Sals-gan: Spatially-adaptive latent space in stylegan for real image embedding. In: Proceedings of the 29th ACM International Conference on Multimedia. pp. 5176–5184 (2021)
  * [55] Zhang, R., Isola, P., Efros, A.A., Shechtman, E., Wang, O.: The unreasonable effectiveness of deep features as a perceptual metric. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 586–595 (2018)
  * [56] Zhu, J., Shen, Y., Zhao, D., Zhou, B.: In-domain gan inversion for real image editing. Lecture Notes in Computer Science p. 592–608 (2020), http://dx.doi.org/10.1007/978-3-030-58520-4_35
  * [57] Zhu, J.Y., Park, T., Isola, P., Efros, A.A.: Unpaired image-to-image translation using cycle-consistent adversarial networks. In: Proceedings of the IEEE international conference on computer vision. pp. 2223–2232 (2017)

##  Appendix 0.A Additional qualitative results

|  |  |  |
---|---|---|---|---
|  |  |  |
|  |  |  |
|  |  |  |
|  |  |  |
GT | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | Ours
Figure 10: Visual comparison of image reconstruction quality on the AFHQ-Wild dataset. +Age |  |  |  |  |
---|---|---|---|---|---
-Age |  |  |  |  |
+Pose |  |  |  |  |
-Pose |  |  |  |  |
+Smile |  |  |  |  |
-Smile |  |  |  |  |
| GT | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | Ours
Figure 11: Additional Pose, smile and age editing using InterFaceGAN [42] of images from the CelebA-HQ dataset. +Grass |  |  |  |  |
---|---|---|---|---|---
+Reflect |  |  |  |  |
+Color |  |  |  |  |
+Model |  |  |  |  |
| GT | $\text{ReStyle}_{\text{pSp}}$ | $\text{ReStyle}_{\text{e4e}}$ | HyperStyle | Ours
Figure 12: Additional visual comparison of editing quality (Stanford Cars). Edits were obtained using GANSpace [18] Rider |  |  |  |
---|---|---|---|---
Color |  |  |  |
| GT | e4e | $\text{ReStyle}_{\text{e4e}}$ | Ours
Figure 13: Visual comparison of editing quality (LSUN Horses). Edits were
obtained using GANSpace [18]


#  A note on the modified $q$-Genocchi numbers and polynomials with weight
$\left(\alpha,\beta\right)$ and their interpolation function at negative
integers

Serkan Aracı  University of Gaziantep, Faculty of Science and Arts, Department
of Mathematics, 27310 Gaziantep, TURKEY<EMAIL_ADDRESS>,  Mehmet Açıkgöz
University of Gaziantep, Faculty of Science and Arts, Department of
Mathematics, 27310 Gaziantep, TURKEY<EMAIL_ADDRESS>,  Feng Qi
Department of Mathematics, College of Science, Tianjin Polytechnic University,
Tianjin 300160, China<EMAIL_ADDRESS>and  Hassan Jolany  School of
Mathematics, Statistics and Computer Science, University of Tehran, Iran
<EMAIL_ADDRESS>
(Date: December 12, 2011)

###### Abstract.

The purpose of this paper concerns to establish modified $q$-Genocchi numbers
and polynomials with weight ($\alpha$,$\beta$). In this paper we investigate
special generalized $q$-Genocchi polynomials and we apply the method of
generating function, which are exploited to derive further classes of
$q$-Genocchi polynomials and develop $q$-Genocchi numbers and polynomials. By
using the Laplace-Mellin transformation integral, we define $q$-Zeta function
with weight ($\alpha$,$\beta$) and by presenting a link between $q$-Zeta
function with weight ($\alpha$,$\beta$) and $q$-Genocchi numbers with weight
($\alpha$,$\beta$) we obtain an interpolation formula for the $q$-Genocchi
numbers and polynomials with weight ($\alpha$,$\beta$). Also we derive
distribution formula (Multiplication Theorem) and Witt’s type formula for
modified $q$-Genocchi numbers and polynomials with weight ($\alpha$,$\beta$)
which yields a deeper insight into the effectiveness of this type of
generalizations for $q$-Genocchi numbers and polynomials. Our new generating
function possess a number of interesting properties which we state in this
paper.

###### Key words and phrases:

Genocchi numbers and polynomials, $q$-Genocchi numbers and polynomials,
$q$-Genocchi numbers and polynomials with weight $\alpha$

###### 2000 Mathematics Subject Classification:

Primary 46A15, Secondary 41A65

##  1\. Introduction, Definitions and Notations

Recently, $q$-calculus has served as a bridge between mathematics and physics.
Therefore, there is a significant increase of activity in the area of the
$q$-calculus due to applications of the $q$-calculus in mathematics,
statistics and physics. The majority of scientists in the world who use
$q$-calculus today are physicists. $q$-Calculus is a generalization of many
subjects, like hypergeometric series, generating functions, complex analysis,
and particle physics. In short, $q$-calculus is quite a popular subject today.
One of Important Branch of $q$-calculus in number theory is $q$-type of
special generating functions, for instance $q$-Bernoulli numbers, $q$-Euler
numbers, and $q$-Genocchi numbers, here we introduce a new class of $q$-type
generating function. We introduce $q$-Genocchi numbers with weight
$\left(\alpha,\beta\right)$. When we define a new class of generating
functions like, $q$-Genocchi numbers with weight $\left(\alpha,\beta\right)$,
then we face to with this question that “can we define a new $q$-Zeta type
function in related of this new class of $q$-type generating function?”. We
give a positive answer for our new class of numbers and polynomials. More
precisely we show that our $q$-type generating function is generalization of
the Hurwitz Zeta function. Historically many authors have tried to give
$q$-analogues of the Riemann Zeta function $\zeta\left(s\right)$, and its
related functions. By just following the method of Kaneko et al. [M. Kaneko,
N. Kurokawa and M. Wakayama, A variation of Euler’s approach to the Riemann
Zeta function, Kyushu J. Math. 57 (2003), 175–192], who mainly used Euler-
Maclaurin summation formula to present and investigate a $q$-analogue of the
Riemann zeta function $\zeta\left(s\right)$, and gave a good and reasonable
explanation that their $q$-analogue may be a best choice. They also commented
that $q$-analogue of $\zeta\left(s\right)$ can be achieved by modifying their
method. Furthermore it is clear that $q$-Genocchi polynomials of weight
$\left(\alpha,\beta\right)$ are in a class of orthogonal polynomials and we
know that most such special functions that are orthogonal are satisfied in
multiplication theorem, so in this present paper we show this property is true
for $q$-Genocchi polynomials of weight $\left(\alpha,\beta\right)$. In this
introductory section, we present the definitions and notations (and some of
the Important properties and characteristics) of the various special
functions, polynomials and numbers, which are potentially useful in the
remainder of the paper.

Assume that $p$ be a fixed odd prime number. Throughout this paper we use the
following notations. By $\mathbb{Z}_{p}$ we denote the ring of $p$-adic
rational integers, $\mathbb{Q}$ denotes the field of rational numbers,
$\mathbb{Q}_{p}$ denotes the field of $p$-adic rational numbers, and
$\mathbb{C}_{p}$ denotes the completion of algebraic closure of
$\mathbb{Q}_{p}$. Let $\mathbb{N}$ be the set of natural numbers and
$\mathbb{Z}_{+}=\mathbb{N}\cup\left\\{0\right\\}.$ Let $v_{p}$ be the
normalized exponential valuation of $\mathbb{C}_{p}$ with
$\left|p\right|_{p}=p^{-v_{p}\left(p\right)}=p^{-1}.$ When one speaks of
$q$-extension, $q$ is considered in many ways such as an indeterminate, a
complex number $q\in\mathbb{C}$ or $p$-adic number $q\in\mathbb{C}_{p}.$ If
$q\in\mathbb{C}$ one normally assume that $\left|q\right|<1.$ If
$q\in\mathbb{C}_{p},$ we assume that $\left|1-q\right|_{p}<p^{-\frac{1}{p-1}}$
so that $q^{x}=\exp\left(x\log q\right)$ for $\left|x\right|_{p}\leq 1.$ We
use the following notation as follows:

$\left[x\right]_{q}=\frac{1-q^{x}}{1-q}\text{,
}\left[x\right]_{-q}=\frac{1-\left(-q\right)^{x}}{1+q}$

Note that $\lim_{q\rightarrow 1}\left[x\right]_{q}=x$; cf. [1-24].

For a fixed positive integer $d$ with $\left(d,f\right)=1,$ we set

$\displaystyle X$ $\displaystyle=$ $\displaystyle
X_{d}=\lim_{\overleftarrow{N}}\mathbb{Z}/dp^{N}\mathbb{Z},$ $\displaystyle
X^{\ast}$ $\displaystyle=$
$\displaystyle\underset{\underset{\left(a,p\right)=1}{0<a<dp}}{\cup}a+dp\mathbb{Z}_{p}$

and

$a+dp^{N}\mathbb{Z}_{p}=\left\\{x\in X\mid x\equiv
a\left(\mathop{\mathrm{m}od}dp^{N}\right)\right\\},$

where $a\in\mathbb{Z}$ satisfies the condition $0\leq a<dp^{N}.$

By use Koblitz [N. Koblitz, $p$-adic Numbers $p$-adic Analysis and Zeta
Functions, Springer-Verlag, New York Inc, 1977] notations, A $p$-adic
distribution $\mu$ on $X$ is a $\mathbb{Q}_{p}$-linear vector space
homomorphism from the $\mathbb{Q}_{p}$-vector space of locally constant
functions on $X$ to $\mathbb{Q}_{p}$. If $f:X\rightarrow\mathbb{Q}_{p}$ is
locally constant, instead of writing $\mu\left(f\right)$ for the value of
$\mu$ at $f$, we usually write $\int f\mu$. Also it is known that we can write
$\mu_{q}$ as follows:

$\mu_{q}\left(x+p^{N}\mathbb{Z}_{p}\right)=\frac{q^{x}}{\left[p^{N}\right]_{q}}$

is a distribution on $X$ for $q\in\mathbb{C}_{p}$ with
$\left|1-q\right|_{p}\leq 1.$ For

$f\in UD\left(\mathbb{Z}_{p}\right)=\left\\{f\mid
f:\mathbb{Z}_{p}\rightarrow\mathbb{C}_{p}\text{ is uniformly differentiable
function}\right\\},$

the fermionic $p$-adic $q$-integral on $\mathbb{Z}_{p}$ is defined by T. Kim
as follows:

$\displaystyle I_{-q}\left(f\right)$ $\displaystyle=$
$\displaystyle\int_{\mathbb{Z}_{p}}f\left(x\right)d\mu_{-q}\left(x\right)=\lim_{N\rightarrow\infty}\sum_{x=0}^{p^{N}-1}f\left(x\right)\mu_{-q}\left(x+p^{N}\mathbb{Z}_{p}\right)$
$\displaystyle=$
$\displaystyle\lim_{N\rightarrow\infty}\frac{1}{\left[p^{N}\right]_{-q}}\sum_{x=0}^{p^{N}-1}\left(-1\right)^{x}f\left(x\right)q^{x}$

Let $q\rightarrow 1,$ then we have fermionic integration on $\mathbb{Z}_{p}$
as follows:

$I_{-1}\left(f\right)=\int_{\mathbb{Z}_{p}}f\left(x\right)d\mu_{-1}\left(x\right)=\lim_{N\rightarrow\infty}\sum_{x=0}^{p^{N}-1}\left(-1\right)^{x}f\left(x\right),$

So by applying $f\left(x\right)=e^{xt},$ we get

(1.2)
$t\int_{\mathbb{Z}_{p}}e^{tx}d\mu_{-1}\left(x\right)=\frac{2t}{e^{t}+1}=\sum_{n=0}^{\infty}G_{n}\frac{t^{n}}{n!}$

Where $G_{n}$ are Genocchi numbers. By using (1.2), we have

$\int_{\mathbb{Z}_{p}}e^{xt}d\mu_{-1}\left(x\right)=\sum_{n=0}^{\infty}\frac{G_{n+1}}{n+1}\frac{t^{n}}{n!}$

so from above, we obtain

$\sum_{n=0}^{\infty}\left(\int_{\mathbb{Z}_{p}}x^{n}d\mu_{-1}\left(x\right)\right)\frac{t^{n}}{n!}=\sum_{n=0}^{\infty}\left(\frac{G_{n+1}}{n+1}\right)\frac{t^{n}}{n!}$

By comparing coefficients of $\frac{t^{n}}{n!}$ on both sides of the above
equation it is fairly straightforward to deduce,

$\frac{G_{n+1}}{n+1}=\int_{\mathbb{Z}_{p}}x^{n}d\mu_{-1}\left(x\right).$

The definition of modified $q$-Euler numbers are given by

(1.3) $\varepsilon_{0,q}=\frac{\left[2\right]_{q}}{2},\text{
}\left(q\varepsilon+1\right)^{k}-\varepsilon_{k,q}=\left\\{\QATOP{\left[2\right]_{q},\text{
}k=0}{0,\text{ }k>0}\right.$

with usual the convention about replacing $\varepsilon^{k}$ by
$\varepsilon_{k,q}$ cf. [15],[16]. It was known that the modified $q$-euler
numbers can be represented by $p$-adic $q$-integral on $\mathbb{Z}_{p}$ as
follows:

$\varepsilon_{n,q}=\int_{\mathbb{Z}_{p}}q^{-t}\left[t\right]_{q}^{n}d\mu_{-q}\left(t\right).$

In [3,14,15,17], $q$-Genocchi numbers are defined as follows:

(1.4) $G_{0,q}=0,\text{ and
}q\left(qG_{q}+1\right)^{n}+G_{n,q}=\left\\{\QATOPD..{\left[2\right]_{q},n=1}{0,\text{
\ \ \ }n>1}\right.$

with the usual convention of replacing $\left(G_{q}\right)^{n}$ by $G_{n,q}.$

In [6], $\left(h,q\right)$-Genocchi numbers are indicated as:

$G_{0,q}^{\left(h\right)}=0,\text{ and
}q^{h-2}\left(qG_{q}^{\left(h\right)}+1\right)^{n}+G_{n,q}^{\left(h\right)}=\left\\{\QATOP{\left[2\right]_{q},\text{
}n=1}{0,\text{ \ \ \ }n>1,}\right.$

with the usual convention about replacing
$\left(G_{q}^{\left(h\right)}\right)^{n}$ by $G_{n,q}^{\left(h\right)}.$

Recently, for $n\in\mathbb{Z}_{+},$ Araci et al. are considered weighted
$q$-Genocchi numbers by

(1.5) $\widetilde{G}_{0,q}^{\left(\alpha\right)}=0,\text{
}q^{1-\alpha}\left(q\widetilde{G}_{q}^{\left(\alpha\right)}+1\right)^{n}+\widetilde{G}_{n,q}^{\left(\alpha\right)}=\left\\{\QATOP{\left[2\right]_{q},\text{
}n=1}{0,\text{ \ \ \ \ \ }n\neq 1,}\right.$

with the usual convention about replacing $\left(\widetilde{G}_{q}\right)^{n}$
by $\widetilde{G}_{n,q}$ (for more information, see [1])

For $\alpha,n\in\mathbb{Z}_{+}$ and $h\in\mathbb{N},$ Araci et al. [2] defined
weighted $\left(h,q\right)$-Genocchi numbers as follows:

$\widetilde{G}_{n+1,q}^{\left(\alpha,h\right)}=\int_{\mathbb{Z}_{p}}q^{\left(h-1\right)x}\left[x\right]_{q^{\alpha}}^{n}d\mu_{-q}\left(x\right).$

Taekyun Kim, by using $p$-adic $q$-integral on $\mathbb{Z}_{p}$, introduced a
new class of numbers and polynomials. He added a weight on $q$-Bernoulli
numbers and polynomials and defined $q$-Bernoulli numbers with weight
$\alpha$. He is given some interesting properties concerning $q$-Bernoulli
numbers and polynomials with weight $\alpha$. After, by using $p$-adic
$q$-integral on $\mathbb{Z}_{p},$ several mathematicians started to study on
this new branch of generating function theory and extended most of the
symmetric properties of $q$-Bernoulli numbers and polynomials to $q$-Bernoulli
numbers and polynomials with weight $\alpha$ (for more informations, see
[1],[2],[4],[5],[6],[7],[8],[9],[10],[11],[12]). With the same motivation, we
also introduce modified $q$-Genocchi numbers and polynomials with weight
$\left(\alpha,\beta\right).$ Also, we give some interesting properties this
type of polynomials. Furthermore, we derive the $q$-extensions of zeta type
functions with weight $\left(\alpha,\beta\right)$ from the Mellin
transformation to this generating function which interpolates the $q$-Genocchi
polynomials with weight $\left(\alpha,\beta\right)$ at negative integers.

##  2\.  Modified $q$-Genocchi numbers and polynomials with weight
$\left(\alpha,\beta\right)$

In this section, we derive some interesting properties Modified $q$-Genocchi
numbers and polynomials with weight $\left(\alpha,\beta\right)$.

######  Lemma 1.

For $n\in\mathbb{Z}_{+},$we obtain

(2.1) $I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f_{n}\right)+\left(-1\right)^{n-1}I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)=\left[2\right]_{q^{\beta}}\sum_{l=0}^{n-1}\left(-1\right)^{n-l-1}f\left(l\right),$

###### Proof.

Let be $f_{n}\left(x\right)=f\left(x+n\right)$ and
$I_{-q}^{\left(\beta\right)}\left(f\right)=\int_{\mathbb{Z}_{p}}f\left(x\right)d\mu_{-q^{\beta}}\left(x\right)$
by the (1), we easily get

(2.2) $\displaystyle-I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f_{1}\right)$ $\displaystyle=$
$\displaystyle\lim_{N\rightarrow\infty}\frac{1}{\left[p^{N}\right]_{-q^{\beta}}}\sum_{x=0}^{p^{N}-1}f\left(x+1\right)\left(-1\right)^{x}$
$\displaystyle=$
$\displaystyle\lim_{N\rightarrow\infty}\frac{1}{\left[p^{N}\right]_{-q^{\beta}}}\sum_{x=0}^{p^{N}-1}f\left(x\right)\left(-1\right)^{x}-\left[2\right]_{q^{\beta}}\lim_{N\rightarrow\infty}\frac{f\left(p^{N}\right)+f\left(0\right)}{1+q^{\beta
p^{N}}}$ $\displaystyle=$ $\displaystyle
I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)-\left[2\right]_{q^{\beta}}f\left(0\right)$

and

$\displaystyle I_{-q}^{\left(\beta\right)}\left(q^{-\beta x}f_{2}\right)$
$\displaystyle=$ $\displaystyle\int_{\mathbb{Z}_{p}}q^{-\beta
x}f\left(x+2\right)d\mu_{-q^{\beta}}\left(x\right)=\lim_{N\rightarrow\infty}\frac{1}{\left[p^{N}\right]_{-q^{\beta}}}\sum_{x=0}^{p^{N}-1}f\left(x+2\right)\left(-1\right)^{x}$
$\displaystyle=$ $\displaystyle I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)+\left[2\right]_{q^{\beta}}\lim_{N\rightarrow\infty}\frac{-f\left(0\right)+f\left(1\right)-f\left(p^{N}\right)+f\left(p^{N}+1\right)}{1+q^{\beta
p^{N}}}$ $\displaystyle=$ $\displaystyle
I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)+\left[2\right]_{q^{\beta}}\left(f\left(1\right)-f\left(0\right)\right)$

Thus, we have

$I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f_{2}\right)-I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)=\left[2\right]_{q^{\beta}}\sum_{l=0}^{1}\left(-1\right)^{1-l}f\left(l\right)$

By continuing this process, we arrive at the desired result.

######  Definition 1.

Let $\alpha,n,\beta\in\mathbb{Z}_{+}.$ We define modified $q$-Genocchi numbers
with weight $\left(\alpha,\beta\right)$ as follows:

(2.3)
$\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}}{n+1}=\left[2\right]_{q^{\beta}}\sum_{m=0}^{\infty}\left(-1\right)^{m}\left[m\right]_{q^{\alpha}}^{n}$

######  Theorem 1.

For $\alpha,n,\beta\in\mathbb{Z}_{+},$ we get

(2.4)
$\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}}{n+1}=\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\frac{1}{1+q^{\alpha
l}}$

###### Proof.

By (2.3), we develop as follows:

$\displaystyle\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}}{n+1}$
$\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{m=0}^{\infty}\left(-1\right)^{m}\left(1-q^{m\alpha}\right)^{n}$
$\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{m=0}^{\infty}\left(-1\right)^{m}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\left(q^{m\alpha}\right)^{l}$
$\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\sum_{m=0}^{\infty}\left(-1\right)^{m}q^{m\alpha
l}$ $\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\frac{1}{1+q^{\alpha
l}}.$

Thus, we complete the proof of Theorem.

By the following Theorem, we get Witt’s type formula of this type polynomials.

######  Theorem 2.

For $\beta,\alpha,n\in\mathbb{Z}_{+},$ we get

(2.5)
$\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}}{n+1}=\int_{\mathbb{Z}_{p}}q^{-\beta
x}\left[x\right]_{q^{\alpha}}^{n}d\mu_{-q^{\beta}}\left(x\right).$

###### Proof.

By using $p$-adic $q$-integral on $\mathbb{Z}_{p}$, namely, replace $f(x)$ by
$q^{-\beta x}\left[x\right]_{q^{\alpha}}^{n}$ and
$\mu_{-q}\left(x+p^{N}\mathbb{Z}_{p}\right)$ by
$\mu_{-q^{\beta}}\left(x+p^{N}\mathbb{Z}_{p}\right)$ into (1), we get

$\displaystyle\int_{\mathbb{Z}_{p}}q^{-\beta
x}\left[x\right]_{q^{\alpha}}^{n}d\mu_{-q^{\beta}}\left(x\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\int_{\mathbb{Z}_{p}}q^{\alpha
lx-\beta x}d\mu_{-q^{\beta}}\left(x\right)$ $\displaystyle=$
$\displaystyle\frac{1}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\lim_{N\rightarrow\infty}\frac{1}{\left[p^{N}\right]_{-q^{\beta}}}\sum_{x=0}^{p^{N}-1}\left(-q^{\alpha
l}\right)^{x}$ $\displaystyle=$
$\displaystyle\frac{1}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\frac{\left[2\right]_{q^{\beta}}}{1+q^{\alpha
l}}\lim_{N\rightarrow\infty}\frac{1+\left(q^{\alpha
l}\right)^{p^{N}}}{1+q^{\beta p^{N}}}$ $\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}\frac{1}{1+q^{\alpha
l}}$

Use of (2.4) and (2), we arrive at the desired result.

The Witt’s type formula of modified $q$-Genocchi numbers with weight
$\left(\alpha,\beta\right)$ asserted by Theorem 2, do aid in translating the
various properties and results involving $q$-Genocchi numbers with weight
$\left(\alpha,\beta\right)$ which we state some of them in this section. We
put $\alpha\rightarrow 1$ and $\beta\rightarrow 1$ into (2.5), we readily see
$\frac{g_{n+1,q}^{\left(1,1\right)}}{n+1}=\varepsilon_{n,q}.$

######  Corollary 1.

Let $C_{q}^{\left(\alpha,\beta\right)}\left(t\right)=\sum_{n=0}^{\infty}$
$g_{n,q}^{\left(\alpha,\beta\right)}\frac{t^{n}}{n!}.$ Then we have

$C_{q}^{\left(\alpha,\beta\right)}\left(t\right)=\left[2\right]_{q^{\beta}}t\sum_{m=0}^{\infty}\left(-1\right)^{m}e^{t\left[m\right]_{q^{\alpha}}}.$

###### Proof.

From (2.3) we easily get,

(2.7) $\int_{\mathbb{Z}_{p}}q^{-\beta
x}e^{t\left[x\right]_{q^{\alpha}}}d\mu_{-q^{\beta}}\left(x\right)=\left[2\right]_{q^{\beta}}t\sum_{m=0}^{\infty}\left(-1\right)^{m}e^{t\left[m\right]_{q^{\alpha}}}$

By expression (2.7), we have

$\sum_{n=0}^{\infty}g_{n,q}^{\left(\alpha,\beta\right)}\frac{t^{n}}{n!}=\left[2\right]_{q^{\beta}}t\sum_{m=0}^{\infty}\left(-1\right)^{m}e^{t\left[m\right]_{q^{\alpha}}}$

Thus, we complete the proof of Theorem.

Now, we consider the modified $q$-Genocchi polynomials polynomials with weight
$\alpha$ as follows:

(2.8)
$\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}(x)}{n+1}=\int_{\mathbb{Z}_{p}}q^{-\beta
t}\left[x+t\right]_{q^{\alpha}}^{n}d\mu_{-q^{\beta}}\left(t\right),\text{ \
}n\in\mathbb{N}\text{ and }\alpha\in\mathbb{Z}_{+}$

From expression (2.8), we see readily

(2.9) $\displaystyle\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}(x)}{n+1}$
$\displaystyle=$
$\displaystyle\frac{\left[2\right]_{q^{\beta}}}{\left(1-q^{\alpha}\right)^{n}}\sum_{l=0}^{n}\binom{n}{l}\left(-1\right)^{l}q^{\alpha
lx}\frac{1}{1+q^{\alpha l}}$ $\displaystyle=$
$\displaystyle\left[2\right]_{q^{\beta}}\sum_{m=0}^{\infty}\left(-1\right)^{m}\left[m+x\right]_{q^{\alpha}}^{n}$

Let
$C_{q}^{\left(\alpha,\beta\right)}\left(t,x\right)=\sum_{n=0}^{\infty}g_{n,q}^{\left(\alpha,\beta\right)}(x)\frac{t^{n}}{n!}.$
Then we have

(2.10) $\displaystyle C_{q}^{\left(\alpha,\beta\right)}\left(t,x\right)$
$\displaystyle=$
$\displaystyle\left[2\right]_{q^{\beta}}t\sum_{m=0}^{\infty}\left(-1\right)^{m}e^{t\left[m+x\right]_{q^{\alpha}}}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}g_{n,q}^{\left(\alpha,\beta\right)}\left(x\right)\frac{t^{n}}{n!}.$

By Lemma 1, we get the following Theorem:

######  Theorem 3.

For $m\in\mathbb{N},$and $\alpha,\beta,n\in\mathbb{Z}_{+},$ we get

$\frac{g_{m+1,q}^{\left(\alpha,\beta\right)}}{m+1}+\left(-1\right)^{n-1}\frac{g_{m+1,q}^{\left(\alpha,\beta\right)}\left(n\right)}{m+1}=\left[2\right]_{q^{\beta}}\sum_{l=0}^{n-1}\left(-1\right)^{n-l-1}\left[l\right]_{q^{\alpha}}^{m}$

###### Proof.

By applying Lemma 1 the methodology and techniques used above in getting some
identities for the generating functions of the modified $q$-Genocchi numbers
and polynomials with weight $\left(\alpha,\beta\right),$ we arrive at the
desired result.

######  Theorem 4.

The following identity holds:

$g_{0,q}^{\left(\alpha,\beta\right)}=0,\text{ and \
}g_{n,q}^{\left(\alpha,\beta\right)}\left(1\right)+g_{n,q}^{\left(\alpha,\beta\right)}=\left\\{\QATOP{\left[2\right]_{q^{\beta}},\text{if
}n=1,}{0,\text{ if }n>1.}\right.$

###### Proof.

In (2.2) it is known that

$I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f_{1}\right)+I_{-q}^{\left(\beta\right)}\left(q^{-\beta
x}f\right)=\left[2\right]_{q^{\beta}}f\left(0\right)$

If we take $f(x)=e^{t\left[x\right]_{q^{\alpha}}},$ then we have

(2.11) $\displaystyle\left[2\right]_{q^{\beta}}$ $\displaystyle=$
$\displaystyle\int_{\mathbb{Z}_{p}}q^{-\beta
x}e^{t\left[x+1\right]_{q^{\alpha}}}d\mu_{-q^{\beta}}\left(x\right)+\int_{\mathbb{Z}_{p}}q^{-\beta
x}e^{t\left[x\right]_{q^{\alpha}}}d\mu_{-q^{-\beta}}\left(x\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\left(g_{n,q}^{\left(\alpha,\beta\right)}\left(1\right)+g_{n,q}^{\left(\alpha,\beta\right)}\right)\frac{t^{n-1}}{n!}$

Therefore, we get the Proof of Theorem.

######  Theorem 5.

For $d\equiv 1\left(\mathop{\mathrm{m}od}2\right)$,
$\alpha,\beta\in\mathbb{Z}_{+}$ and $n\in\mathbb{N},$ we get,

$g_{n,q}^{\left(\alpha,\beta\right)}\left(dx\right)=\frac{\left[d\right]_{q^{\alpha}}^{n-1}}{\left[d\right]_{-q^{\beta}}}\sum_{a=0}^{d-1}\left(-1\right)^{a}g_{n,q^{d}}^{\left(\alpha,\beta\right)}\left(x+\frac{a}{d}\right).$

###### Proof.

From (2.8), we can easily derive the following (2.12)

(2.12) $\displaystyle\int_{\mathbb{Z}_{p}}q^{-\beta
t}\left[x+t\right]_{q^{\alpha}}^{n}d\mu_{-q^{\beta}}\left(t\right)$
$\displaystyle=$
$\displaystyle\frac{\left[d\right]_{q^{\alpha}}^{n}}{\left[d\right]_{-q^{\beta}}}\sum_{a=0}^{d-1}\left(-1\right)^{a}\int_{\mathbb{Z}_{p}}q^{-\beta
t}\left[\frac{x+a}{d}+t\right]_{q^{d\alpha}}^{n}d\mu_{\left(-q^{d}\right)^{\beta}}\left(t\right)$
$\displaystyle=$
$\displaystyle\frac{\left[d\right]_{q^{\alpha}}^{n}}{\left[d\right]_{-q^{\beta}}}\sum_{a=0}^{d-1}\left(-1\right)^{a}\frac{g_{n+1,q^{d}}^{\left(\alpha,\beta\right)}\left(\frac{x+a}{d}\right)}{n+1}.$

So, by applying expression (2.12), we get at the desired result and proof is
complete.

##  3\. Interpolation function of the polynomials
$g_{n,q}^{\left(\alpha,\beta\right)}\left(x\right)$

In this section, we derive the interpolation function of the generating
functions of modified $q$-Genocchi polynomials with weight $\alpha$ and we
give the value of $q$-extension zeta function with weight
$\left(\alpha,\beta\right)$ at negative integers explicitly. For
$s\in\mathbb{C}$, by applying the Mellin transformation to (2.10), we obtain

$\displaystyle\xi^{\left(\alpha,\beta\right)}\left(s,x\mid q\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\Gamma\left(s\right)}\int_{0}^{\infty}t^{s-2}\left\\{-C_{q}^{\left(\alpha,\beta\right)}\left(-t,x\right)\right\\}dt$
$\displaystyle=$
$\displaystyle\left[2\right]_{q^{\beta}}\sum_{m=0}^{\infty}\left(-1\right)^{m}\frac{1}{\Gamma\left(s\right)}\int_{0}^{\infty}t^{s-1}e^{-t\left[m+x\right]_{q^{\alpha}}}dt$

where $\Gamma\left(s\right)$ is Euler gamma function. We have

$\xi^{\left(\alpha,\beta\right)}\left(s,x\mid
q\right)=\left[2\right]_{q^{\beta}}\sum_{m=0}^{\infty}\frac{\left(-1\right)^{m}}{\left[m+x\right]_{q^{\alpha}}^{s}}$

So, we define $q$-extension zeta function with weight
$\left(\alpha,\beta\right)$ as follows:

######  Definition 2.

For $s\in\mathbb{C}$ and $\alpha,\beta\in\mathbb{N},$ we have

(3.1) $\xi^{\left(\alpha,\beta\right)}\left(s,x\mid
q\right)=\left[2\right]_{q^{\beta}}\sum_{m=0}^{\infty}\frac{\left(-1\right)^{m}}{\left[m+x\right]_{q^{\alpha}}^{s}}$

$\xi^{\left(\alpha,\beta\right)}\left(s,x\mid q\right)$ can be continued
analytically to an entire function.

Observe that, if $q\rightarrow 1,$ then
$\xi^{\left(\alpha,\beta\right)}\left(s,x\mid 1\right)=\zeta\left(s,x\right)$
which is the Hurwitz- Euler zeta functions. Relation between
$\xi^{\left(\alpha,\beta\right)}\left(s,x\mid q\right)$ and
$g_{n,q}^{\left(\alpha,\beta\right)}\left(x\right)$ are given by the following
theorem:

######  Theorem 6.

For $\alpha,\beta\in\mathbb{N}$ and $n\in\mathbb{N},$ we get

$\xi^{\left(\alpha,\beta\right)}\left(-n,x\mid
q\right)=\frac{g_{n+1,q}^{\left(\alpha,\beta\right)}\left(x\right)}{n+1}.$

###### Proof.

By substituting $s=-n$ into (3.1), we arrive at the desired result.

## References

  * [1] Araci, S., Erdal, D., and Seo, J-J., A study on the fermionic $p$-adic $q$-integral representation on $\mathbb{Z}_{p}$ associated with weighted $q$-Bernstein and $q$-Genocchi polynomials, Abstract and Applied Analysis, Volume 2011, Article ID 649248, 10 pages.
  * [2] Araci, S., Seo, J-J., and Erdal, D., New construction weighted $\left(h,q\right)$-Genocchi numbers and polynomials related to zeta type functions, Discrete Dynamics in Nature and Society, Volume 2011, Article ID 487490, 7 pages, doi:10.1155/2011/487490.
  * [3] Araci, S., Erdal, D.,and Kang, D-J., Some new properties on the $q$-Genocchi numbers and polynomials associated with $q$-Bernstein polynomials, Honam Mathematical J. 33 (2011), no. 2, pp. 261-270.
  * [4] Araci, S., Aslan, N., and Seo, J-J., A Note on the weighted Twisted Dirichlet’s type $q$-Euler numbers and polynomials, Honam Mathematical J. 33 (2011), no. 3, pp. 311-320.
  * [5] Araci, S., Açıkgöz, M., and Seo, J-J., A study on the weighted $q$-Genocchi numbers and polynomials with their Interpolation Function, Accepted in Honam Mathematical Journal.
  * [6] Araci, S., and Açıkgöz, M., and Park, K-H., Some identities concerning the $\left(h,q\right)$-Genocchi numbers and polynomials via the $p$-adic $q$-integral on $\mathbb{Z}_{p}$ and $q$-Bernstein polynomials,(submitted).
  * [7] Kim, T., On the weighted $q$-Bernoulli numbers and polynomials, Advanced Studies in Contemporary Mathematics 21(2011), no.2, p. 207-215, http://arxiv.org/abs/1011.5305.
  * [8] Kim, T., Lee, S. H., Dolgy, D. V., Ryoo, C. S., A note on the generalized $q$-Bernoulli measures with weight $\alpha$, Abstract and Applied Analysis, Article ID 867217, 9 pages, doi:10.1155/2011/867217.
  * [9] Kim, T., Choi, J., Kim, Y. H., Ryoo, C. S., A note on the weighted $p$-adic $q$-Euler measure on $\mathbb{Z}_{p}$, Advn. Stud. Contemp. Math. 21 (2011), 35-40.
  * [10] Hwang, K-W., Dolgy, D-V., Lee, S. H., and Kim, T., On the Higher-Order $q$-Euler numbers and polynomials with weight $\alpha,$ Discrete Dynamics in Nature and Society, Volume (2011), Article ID 354329, 12 pages.
  * [11] Kim, T., and Choi, J., On the $q$-Bernoulli numbers and polynomials with weight $\alpha$, Abstract and Applied Analysis, Volume 2011 (2011), Article ID 392025, 14 pages.
  * [12] Kim, T., Dolgy, D-V., Lee, B., and Rim S-H., Identities on the weighted $q$-Euler numbers of higher order, Discrete Dynamics in Nature and Society, Volume 2011 (2011), Article ID 918364, 6 pages.
  * [13] Kim, T., On the $q$-extension of Euler and Genocchi numbers, J. Math. Anal. Appl. 326 (2007) 1458-1465.
  * [14] Kim, T., On the multiple $q$-Genocchi and Euler numbers, Russian J. Math. Phys. 15 (4) (2008) 481-486. arXiv:0801.0978v1 [math.NT]
  * [15] Kim, T., The modified $q$-Euler numbers and polynomials, Advn. Stud. Contemp. Math. 16 (2008), 161-170.
  * [16] Ozden, H., Simsek, Y., Rim, S-H., Cangul, I-N., A note on $p$-adic $q$-euler measure, Adv. Stud. Contemp. Math. 14 (2007), 233-239.
  * [17] Kim, T., $q$-Volkenborn integration, Russ. J. Math. phys. 9$\left(2002\right),$ 288-299.
  * [18] Kim, T., $q$-Bernoulli numbers and polynomials associated with Gaussian binomial coefficients, Russ. J. Math. Phys. 15$\left(2008\right),$ 51-57.
  * [19] Kim, T., An invariant $p$-adic $q$-integrals on $\mathbb{Z}_{p}$, Applied Mathematics Letters, vol. 21, pp. 105-108,2008.
  * [20] Kim, T., A Note on the $q$-Genocchi Numbers and Polynomials, Journal of Inequalities and Applications, Article ID 71452, 8 pages, doi:10.1155/2007/71452.
  * [21] Kim, T. Choi, J. Kim, Y. H. and Jang, L. C., On $p$-Adic Analogue of $q$-Bernstein Polynomials and Related Integrals, Discrete Dynamics in Nature and Society, Article ID 179430, 9 pages, doi:10.1155/2010/179430.
  * [22] Kim, T., $q$-Euler numbers and polynomials associated with $p$-adic $q$-integrals, J. Nonlinear Math. Phys., 14 (2007), no. 1, 15–27.
  * [23] Kim, T., New approach to $q$-Euler polynomials of higher order, Russ. J. Math. Phys., 17 (2010), no. 2, 218–225.
  * [24] Kim, T., Some identities on the $q$-Euler polynomials of higher order and $q$-Stirling numbers by the fermionic $p$-adic integral on $\mathbb{Z}_{p}$, Russ. J. Math. Phys., 16 (2009), no.4,484–491.


What is an Algorithm?: a Modern View

Keehang Kwon
Dept. of Computer Engineering, DongA University

<EMAIL_ADDRESS>
Although algorithm is one of the central subjects, there have been little
common understandings of what an algorithm is. For example, Gurevich[1] view
algorithms as abstract state machines, while others view algorithms as
recursors. We promote a third view: it is a combination to these two disparate
views.

This approach – based on computability logic[3] – describes an algorithm as
$A(I,O)$ where $I$ is a set of input services and $O$ an output service. It
leads to the following modern definition:

An algorithm $A$ is a (tree of) sequence of legal moves for providing $O$
using $I$.

In the above, $A$ is written in an imperative language/abstract state machine
and $I,O$ are written in recursors/logical specifications.

##  1 Introduction

There has been a declarative approach to algorithms. In this approach,
algorithms are expressed using other algorithms. This approach includes
recursive algorithms, logical algorithms and computability logical(CoL)
algorithms[3, 4]. Among these, CoL algorithms is the most expressive of all.

Unfortunately, executing declarative algorithms are often slow due to high
nondeterminism in finding proofs. That is, it is often inefficient to
automatically generate proof steps. For this reason, it is often useful for
the programmer to specify proof scripts. In other words, combining imperative
algorithms and declarative ones is often needed.

This paper proposes to use CoLi as a new algorithm language. The
distinguishing feature of CoLi over CoL is that now the programmer is allowed
to provide imperative features.

##  2 Turing machines or Japaridze machines?

The class of Turing machines (TMs) has been a standard model of computation.
It describes an algorithm in the standard form of

$A(i,o)$

where $i,o$ is an input/output value, and $A$ is an internal imperative
algorithm which maps $i$ to $o$. Thus TMs focuses on input-output mappings.

Japaridze[5, 6, 7] proposed a new computing model which we call Japaridze
machines. It is a TM which focuses on its exchanging services(input services
and output services). That is, it describes an algorithm with respect to their
exchanging services. To be specific, it describes an algorithm in the form of

$A(I,O)$

where $I$ is the set of input services and $O$ is the output service and $A$
is an internal imperative algorithm to accomplish $O$ using $I$. For example,
consider a task ”computes 3!”. While the conventional TM would produce 6,
Japaridze machines produce a service/knowledge which is $fact(3,6)$. We call
this approach CoLi algorithms. Despite of its several advantages, it is quite
unfortunate that CoLi algorithms have been largely ignored by academia and
industry.

We compare these two models. First, TM preserve only the input/output behavior
of a function. There is more to an algorithm than the function it computes.
Japaridze machines provides $services$ rather than function outputs. The
notion of services is a big concept which includes knowledge, interactive
services, other complex services.

Second, the single, low abstraction level of the Turing machine inhibits its
ability to describe algorithms concisely. The author of Japaridze machines can
choose an arbitrary set of input services and therefore has flexibility in
choosing the level of abstraction.

Third, given $I$ and $O$, $A$ can automatically be generated by Japaridze
machines. We call the description $(I,O)$ CoL algorithms.

Finally, it is easier to extend Japaridze machines to distributed computation.
A distributed Japaridze machines (also know as computability-logic web[8]) is
a set of Japaridze machines providing services to one another. It is a
promising model for distributed computing with several attractive features
such as local name space and service migrations.

Turing machines lead to the development of assembly languages and C. We now
consider how Japaridze machines could be useful in a new language development.
In the $A(I,O)$ above, note that $A$ is written in imperative languages
whereas $I,O$ are written in logic languages in CoL.

This lead us to a next-generation imperative language where imperative
languages are used as implementation languages and logic languages are used as
specification. This new language is thus closely related to the deep
specification approach to software. An example may be Python with logical
specification of input/output services. That is,

  * •

Turing machines $\Rightarrow$ Assembly languages, C, Python, $\ldots$

  * •

Japaridze machines$\Rightarrow$ Assembly+deep specification, C+deep
specification, $\ldots$

We now consider when we need CoLi algorithms. CoL is a complex language with a
huge yet of useful operations. The design of Japaridze machines aims at
automatically generating an internal algorithm/strategy from given input and
out services. This approach has been successful for various fragments of CoL.
Yet, implementing the full CoL is a totally different story: it seems a
daunting, almost impossible task due to its huge complexity. Accordingly, we
have no other choice but to rely on CoLi algorithms to utilize the full CoL.

##  3 Preliminaries

In this section a brief overview of CoL is given.

There are two players: the machine $\top$ and the environment $\bot$.

There are two sorts of atoms: elementary atoms $p$, $q$, …to represent
elementary games, and general atoms $P$, $Q$, …to represent any, not-
necessarily-elementary, games.

Constant elementary games

$\top$ is always a true proposition, and $\bot$ is always a false proposition.

Negation

$\neg$ is a role-switch operation: For example, $\neg(0=1)$ is true, while
$(0=1)$ is false.

Choice operations

The choice group of operations: $\sqcap$, $\sqcup$, $\sqcap$ and $\sqcup$ are
defined below.

$\mbox{\Large$\sqcap$}xA(x)$ is the game where, in the initial position, only
$\bot$ has a legal move which consists in choosing a value for $x$. After
$\bot$ makes a move $c\in\\{0,1,\ldots\\}$, the game continues as $A(c)$.
$A\sqcap B$ is similar, only here the choice is made between “left” and
“right”. $\sqcup$ and $\sqcup$ are symmetric to $\sqcap$ and $\sqcap$, with
the difference that now it is $\top$ who makes an initial move.

Parallel operations

Playing $A_{1}\wedge\ldots\wedge A_{n}$ means playing the $n$ games
concurrently. In order to win, $\top$ needs to win in each of $n$ games.
Playing $A_{1}\vee\ldots\vee A_{n}$ also means playing the $n$ games
concurrently. In order to win, $\top$ needs to win one of the games. To
indicate that a given move is made in the $i$th component, the player should
prefix it with the string “$i.$”. The operations
$\mbox{\raisebox{-0.28436pt}{\scriptsize$\wedge$}\raisebox{4.55254pt}{\tiny$\mid$}\hskip
2.0pt}A$ means an infinite parallel game $A\wedge\ldots\wedge A\wedge\ldots$.
To indicate that a given move is made in the $i(i>1)$th component, we assume
the player should first replicate $A$ and then prefix it with the string
“$i.$”.

Reduction

$A\rightarrow B$ is defined by $\neg A\vee B$. Intuitively, $A\rightarrow B$
is the problem of reducing $B$ (consequent) to $A$ (antecedent).

##  4 Introducing Directories

Logical formulas are inadequate for locating subformulas. Our approach to
achieving this effect is through the use of directories. For example, consider
the following directory definition.

$/m=p(a)$

where $/m$ is a directory name and $p(a)$ is a formula. In this case, we call
$p(a)$ its “content”. Alternatively, we can view $/m$ as an agent and $p(a)$
as its knowledgebase.

Our directory system is very flexible and is designed to represent both
formulas and cirquents. For example, $/n=!/m\land!/m$ represents that the
directory $/n$ contains $p(a)\land p(a)$. Here $!/m$ is intended to read as “a
copy of the content of $/m$. In contrast, $/o=/m\land/m$ represents that $/o$
contains a cirquent $p(a)\land p(a)$ where two $p(a)$s in $/o$ and $p(a)$ in
$/m$ are $shared$.

As another example, consider the following recursive directory definition.

$/m(0)=q$ $/m(s(X))=p\land!/m(X)$

Given this definition, $p\land(p\land(p\land q)))$ can be represented simply
as $/m(s(s(s(0))))$. We assume in the above that $s$ is the number-successor
function.

Thus, we propose the notion of directorized formulas. They are formulas
enhanced with directories. These formulas are better-suited to structuring
large formulas such as pigeonhole principle formulas. It is interesting to
note that directories also play the role of global variables in imperative
languages and much more.

##  5 CoLi Algorithms

A CoLi algorithm is of the form

$A(I,O)$

where $I=\\{I_{1},\ldots,I_{n}\\}$ is a set of input services and $O$ is an
output service, both written in CoL. $A$ is a winning strategy, i.e., a tree
of runs111 A run is a sequence of moves. written in pseudocode. A run is a
sequence of $S_{1};S_{2};\ldots$ where $S$ is of several kinds. We list some
of them below.

  1. 1.

$l.read(N)$ replaces a subformula $\mbox{\Large$\sqcap$}xF$ at location $l$ by
$F(X/x)$ where $X$ is a new variable. For example, suppose
$\mbox{\Large$\sqcap$}xp(x)$ is at $l$. $l.read(N)$ replaces it by $p(X)$ and
stores $X$ in the global variable $N$.

  2. 2.

$l.write$ replaces $\mbox{\Large$\sqcup$}xF$ at $l$ by $F(W/x)$ where $W$ is a
new global variable. For example, suppose $\mbox{\Large$\sqcup$}xp(x)$ is at
$l$. $l.write$ replaces $\mbox{\Large$\sqcup$}xp(x)$ by $p(W)$. The value of
$W$ is unknown and will later be determined via the unification
process222Global variables are different from variables. The unification
process only deals with global variables.. This technique is well-known in the
logic programming community.

  3. 3.

$choose(l_{1}:r_{1},\ldots,l_{n}:r_{n})$ limits the proof search space to the
given $n$ choices, where each $l_{i}$ denotes a location of some subformula
$H$ and $r_{i}$ is a list of rule candidates to apply to $H$. We often omit
$r_{i}$ when it is obvious.

  4. 4.

$schoose(l_{1}:r_{1},\ldots,l_{n}:r_{n})$ is identical to
$choose(l_{1}:r_{1},\ldots,l_{n}:r_{n})$ with the difference that
$l_{1}:r_{1}$ has the highest priority and $l_{n}:r_{n}$ has the lowest.

  5. 5.

Conditional statements include the if-then-else. Iterational statements
include the for-loop.

  6. 6.

$prove$ tries to extract a winning strategy $S$ from the current
configuration. $execute$ executes $S$.

An internal algorithm $A$ typically is very complex and challenging. It
requires two stages:

  * •

The stage 1 extracts a winning strategy $S$ from the given $(I,O)$. $S$ is
typically nondeterministic and has the form of a tree of runs due to
interactive services. This stage is very difficult due to the complexity of
the proof procedure.

  * •

The stage 2 executes a branch of $S$ which is obtained by interacting with the
user. This stage is easy.

In most cases, stage 1 can be automated by the machine. Unfortunately, there
are cases when $S$ is difficult to extract by the machine but the programmer
knows $S$. In such cases, CoLi would be useful. In writing CoLi algorithms, it
would be painful for the programmer to write $A$ from scratch. Instead, $A$ is
typically written by the programmer in a minimal way, i.e., in the style of
proof scripts. The rest will then be automatically generated by the machine.

##  6 Examples

As an example, we present the factorial algorithm to help understand this
notion. The factorial algorithm can be defined using two input services
$/c,/d$ whose tasks are described below: where the recurrence action is
preceded with $\wedge$$\mid$ .

$/c=fact(0,1)$
$/d=\mbox{\raisebox{-0.28436pt}{\scriptsize$\wedge$}\raisebox{4.55254pt}{\tiny$\mid$}\hskip
2.0pt}\ \mbox{\Large$\sqcap$}x\mbox{\Large$\sqcap$}y(fact(x,y)\rightarrow\
fact(x+1,xy+y))$.
$/query=\mbox{\Large$\sqcap$}y\mbox{\Large$\sqcup$}zfact(y,z)$ % read y and
compute z (which is y! )

Suppose computation tries to solve the $/query$ with respect to $/c,/d$.
Observe that $/query$ is a logical consequence of $/c$ and $/d$ and proving
this fact requires mathematical induction. Extracting a winning strategy for
this problem is quite difficult and nontrivial. Unlike the machine, however, a
winning strategy is obvious to human and is the following: read $y$ in the
/query, make $y$ copies of $/d$, instantiate $x,y$ in each copy of $/d$ and
then compute $z$ which is a logical consequence of these knowledgebase333 In
fact, making a copy of $/d$ occurs on demand, i.e., when the corresponding
$i$th component is not available yet.. The corresponding proof script $Fact$
is shown below:

Algorithm $Fact(\\{/c,/d\\},/query)$ % An algorithm for computing factorial.
/query.read(n);
for i=1 to n;
/d.i.write; % process $\mbox{\Large$\sqcap$}x$ in the $i$th copy of /d.
/d.i.write; % process $\mbox{\Large$\sqcap$}y$ in the $i$th copy of /d.
endfor;
/query.write; % process $\mbox{\Large$\sqcup$}z$ in the query
execute; % invoke the unification procedure

In the above, note that $\mbox{\Large$\sqcap$}y$ in the $/query$ is the major
obstacle in extracting a winning strategy $S$. Once $\mbox{\Large$\sqcap$}y$
has been processed, extracting the rest of $S$ poses no problem. Therefore,
$Fact$ can be simplified to the following:

Algorithm $Fact(\\{/c,/d\\},/query)$ % A shortened algorithm for computing
factorial.
/query.read(n);
prove; % extract a winning strategy from the current configuration.
execute; % invoke the unification procedure.

Proof scripts are also useful for dealing with semidecidable problems. For
example, consider the following:

$/q=\mbox{\raisebox{-0.28436pt}{\scriptsize$\wedge$}\raisebox{4.55254pt}{\tiny$\mid$}\hskip
2.0pt}\mbox{\Large$\sqcup$}xp(x)\vee q(a).$

The above formula is invalid. Unfortunately, a typical proof procedure does
not terminate for this formula, as it repeatedly replicates
$\mbox{\raisebox{-0.28436pt}{\scriptsize$\wedge$}\raisebox{4.55254pt}{\tiny$\mid$}\hskip
2.0pt}\mbox{\Large$\sqcup$}xp(x)$. We can avoid this unpleasant situation by
providing the following proof script which tells the machine not to replicate
it.

/q.1:$\sqcup$-rule; % replicate is disallowed in
$\mbox{\raisebox{-0.28436pt}{\scriptsize$\wedge$}\raisebox{4.55254pt}{\tiny$\mid$}\hskip
2.0pt}\mbox{\Large$\sqcup$}xp(x)$.

In the beginning, the machine first chooses a term $t$ for
$\mbox{\Large$\sqcup$}x$ and obtains $p(t)\vee q(a)$. Then the proof procedure
terminates with the failure.

##  7 Conclusion

Our intention is to raise awareness of the CoLi algorithms as a new tool for
expressing algorithms. We believe it is a tool of real value. Another interest
is in designing a more flexible proof script language.

## References

  * [1] Yuri Grevich.  What is an algorithm?.  Micosoft TR-MSR-TR-2011-116, 2011.
  * [2] G. Japaridze.  The logic of tasks.  Annals of Pure and Applied Logic, 117:263–295, 2002.
  * [3] G. Japaridze.  Introduction to computability logic.  Annals of Pure and Applied Logic, 123:1–99, 2003.
  * [4] G. Japaridze.  Sequential operators in computability logic.  Information and Computation, vol.206, No.12, pp.1443-1475, 2008.
  * [5] G. Japaridze. Computability logic: a formal theory of interaction. In Interactive Computation: The New Paradigm, Goldin D, Smolka S A, Wegner P (eds.), Springer, 2006, pp. 183-223.
  * [6] G. Japaridze. In the beginning was game semantics. In Games: Unifying Logic, Language and Philosophy, Majer O, Pietarinen A -V, Tulenheimo T (eds.), Springer, 2009, pp. 249-350.
  * [7] G. Japaridze. Towards applied theories based on computability logic. Journal of Symbolic Logic, 2010, 75(2): 565-601.
  * [8] K. Kwon. Computability-logic web: an alternative to deep learning. arXiv:2101.09222, 2020.